Toots Thielemans est la première station de métro entièrement nouvelle à être construite dans le cadre du Métro 3. Après les différents travaux préparatoires, la construction de la station et des tunnels de liaison a débuté en octobre 2020. Différentes techniques seront utilisées pour la réalisation.
La station sera construite sous l’avenue de Stalingrad, entre le carrefour avec la petite ceinture et le Palais du Midi avec la méthode « cut & cover ». La construction se fait en deux phases, afin de maintenir une voirie accessible en direction de la place Rouppe. Dans la première phase, les fondations et les murs seront réalisés côté impair de l'avenue.
Dans une deuxième phase, le chantier sera déplacé côté pair. Une fois que la structure de base et la dalle de toiture seront réalisés, les travaux se dérouleront principalement en sous-terrain. Ensuite la surface sera réaménagée. La Ville de Bruxelles a entre-temps constitué un panel de riverains, commerçants et autres usagers du quartier pour définir les priorités pour le futur visage de l'avenue de Stalingrad.
La nouvelle station sera reliée par un passage souterrain partiellement existant à la station Lemonnier, qui sera à son tour entièrement rénové et continuera à servir pour les lignes de tram de la petite ceinture ouest (trams 51 et 82).

La nouvelle station Toots Thielemans sera reliée à l'infrastructure existante près de la Gare du Midi par un nouveau tunnel sous le boulevard Jamar. Ce tunnel sera réalisé du côté des numéros impairs, avec la technique du cut & cover. Dès que les fondations, les murs et la dalle de la toiture auront été réalisés, les travaux se poursuivront en sous-sol. On passera alors au réaménagement de l'espace public. Comme il s'agit d'une route régionale, le réaménagement sera piloté par Bruxelles Mobilité, mais l'intention est d'entamer un processus participatif.

Une autre zone de chantier se trouve au milieu du carrefour de la petite ceinture. La circulation y est réorganisée grâce au grand giratoire qui a été mis en place. À cet endroit, le nouveau tunnel du boulevard Jamar sera relié à la nouvelle station Toots Thielemans. Un couloir souterrain sera également réalisé pour faciliter la correspondance avec la station Lemonnier.
Comme nous sommes confrontés à un sous-sol compliqué, avec plusieurs infrastructures existantes comme l'ancien tunnel tram, de nombreux collecteurs d'égouts et d'autres réseaux souterrains, ceci nécessite un travail de précision. Des techniques spéciales, telles que la congélation du sol, seront utilisées. Ainsi, les eaux souterraines et de surface seront gelées localement afin que les travaux d'excavation et de construction puissent se dérouler en toute sécurité.

La station Toots Thielemans devra également être reliée à l'infrastructure existante en direction de la station d'Anneessens. À cette fin, un tunnel de liaison sera réalisé sous le Palais du Midi. Ce bâtiment historique sera d'abord renforcé à partir des caves, en utilisant la technique du "Jet Grouting", qui consiste à injecter du ciment dans le sol sous haute pression. Par la suite, les parois du tunnel seront réalisées jusqu'à 20 m de profondeur, puis la dalle de toiture.
Pendant ces travaux, une grande partie du bâtiment, notamment la Haute École et le complexe sportif, continuera à fonctionner. Seule une partie des commerçants du rez-de-chaussée doivent temporairement faire place au chantier. Ces commerces ont été relogés, soit ailleurs dans le quartier, soit dans le Stalingrad Village, qui a été construit un peu plus loin sur la berme centrale de l'avenue de Stalingrad. Après les travaux, les caves et le parking du Palais de Midi seront restaurés dans leur état d'origine. Par la suite, les façades de ce bâtiment historique seront également rénovées.