Il palazzo venne costruito fra il 1402 e il 1455 da diversi architetti. Colui che concepì il progetto di base probabilmente è il borgognone Jean Bornoy con la collaborazione di Jacob van Tienen. Quest'ultimo è l'architetto che ne inizia e intraprende la costruzione del primo cantiere. La parte più antica dell'edificio è l'ala sinistra (orientale). Questa parte, con pianta a "L", formata dalla facciata sinistra, l'ala lungo rue Charles Buls e insieme a un piccolo Beffroi, venne da lui eretta fra il 1402 e il 1420. Nel 1444 Carlo il Temerario, futuro erede del titolo di duca di Borgogna e quindi delle Fiandre, decide di ingrandire la costruzione, e posa la prima pietra del nuovo fronte destro (occidentale). L'architetto è sconosciuto, ma si crede sia Willem de Voghel, architetto di città a Bruxelles dal 1452 e autore in questo periodo dell'aula magna del palazzo di Filippo il Buono, oggi scomparso, sul Coudenberg (il "quartiere dei signori" della Bruxelles dell'epoca). L'edificazione del lato occidentale, più corto, sarà terminata cinque anni dopo. Tutta l'intera facciata del municipio presenta una fastosa decorazione scultorea di pinnacoli, baldacchini e statue. Queste ultime rappresentanti I duchi di Brabante, santi, figure allegoriche e Profeti, sono delle copie eseguite durante i profondi restauri del 1840. Gli originali, i Profeti, risalenti al 1390 ed eseguiti dalla scuola di Claus Sluter, si trovano al Museo della città di Bruxelles che ha sede nella Maison du Roi. Originali sono invece le statue del portale principale, anch'esse della scuola di Claus Sluter. Tra gli scultori che diedero il loro contributo si può menzionare Paul Bouré.

 

Con il pesantissimo bombardamento di Bruxelles del 1695 da parte delle truppe francesi del maresciallo de Villeroy e l'incendio scaturitovi, il municipio subì gravissimi danni, perdendo tutti gli interni, gli archivi e le collezioni d'arte ivi contenuti. Solo la facciata e la torre si salvarono. Vennero immediatamente ricostruite le parti perse e furono anche aggiunte due ali posteriori a chiudere la struttura, fino ad allora con pianta a "L", in un quadrilatero con corte centrale; completata da Corneille van Nerven, nel 1712.

 

Il palazzo comunale, oltre che alle autorità municipali, ospitò anche le assemblee degli Staten van Brabant (Stati del Brabante), sorta di Stati generali. In seguito all'annessione del Brabante e delle Diciassette province dei Paesi Bassi, al Ducato di Borgogna, nel municipio di Bruxelles si tenerono anche gli Stati generali dei Paesi Bassi, riunitisi fino al 1795. Dal 1830, durante la rivoluzione belga, un governo provvisorio si riuniva in questo luogo.

 

Il Beffroi di Bruxelles costituisce uno dei capolavori assoluti dell'architettura gotica secondo lo stile Gotico brabantino, tra le più belle torri civiche del mondo.

 

Venne eretta fra il 1449 e il 1454 da Jan van Ruysbroeck, architetto di corte di Filippo il Buono, a sostituzione del precedente Beffroi, più piccolo. Alta ben 96 metri si presenta come una forte torre quadrata coronata da una svettante guglia ottagonale traforata circondata da quattro torrette angolari. Lo slancio, la grazia delle forme e il suo straordinario equilibrio di masse le valsero fin dall'inizio l'appellativo di Tour Inimitable. In cima alla guglia vi è il gruppo di San Michele e il diavolo, emblema della città; statua in rame dorato alta circa 5 metri, opera del 1454 di Marten van Rode.