Elle se dresse au carrefour de deux anciennes routes importantes (Routes : Flandre vers Cologne et Anvers vers Mons par Bruxelles). Ce carrefour était situé sur une colline, le Treurenberg (anc. Molenberg). On trouve une mention de Bruxelles dans les gestes des évêques de Cambrai (diocèse dont elle dépendait): l'évêque Vindicien devient malade près de Bruxelles peu avant sa mort en 695 (source du xie siècle : Gesta pontificium Cameracensius, PL 149, 46: cum egrotaret apud Brosselam). 

Lambert II, comte de Louvain, et sa femme Oda de Verdun, fondèrent en 1047 un chapitre de 12 chanoines dans l'église Saint-Michel (d’où le nom de « collégiale ») et y firent transporter les reliques de sainte Gudule jusqu'alors conservées dans l'église Saint-Géry qui occupait, jusqu'à la révolution française, l'emplacement actuel des halles Saint-Géry.

Collégiale Sainte-Gudule à Bruxelles, dessin par Léon van Dievoet

En 1072, l'église Saint-Michel fut de nouveau consacrée (probablement parce qu'elle avait été affectée par un incendie peu de temps avant). En 1200, sous l'impulsion d'Henri Ier de Brabant, l'église fut restaurée et agrandie par la construction d'un avant-corps occidental, accompagné de deux tours rondes. En 1226, le duc de Brabant Henri II décida la construction d'une collégiale gothique qui ne s'acheva qu'au début du xvie siècle peu après la naissance de Charles Quint. Certaines chapelles s'y ajoutèrent aux xvie et xviie siècles.

La construction de l'édifice actuel débute par le chœur en 1226. La nef et le transept qui datent des xive et xve siècles sont de style gothique brabançon. La façade est surmontée de deux tours et date des années 1470-1485.

Ce n'est qu'en 1962 que Bruxelles, jusque-là dépendante de l'archevêché de Malines où résidait le primat de Belgique, fut associée à ce siège épiscopal sous le titre de diocèse de Malines-Bruxelles. C'est ainsi que la collégiale fut promue au rang de cathédrale. 

D'importants travaux de restauration ont permis en 1991 de redécouvrir sous la cathédrale les vestiges de l'antique collégiale primitive, dont la crypte romane, épargnée par la construction de l'édifice gothique de 1226 et par les sépultures postérieures. Le placement d'une dalle au-dessus de ces vestiges rend possible la visite de ce nouveau site archéologique.