Selon la légende, Saint-Denis, premier évêque de Paris, aurait été décapité à Montmartre (étymologiquement, mont des martyrs) vers l'an 250. Il aurait alors effectué, à pied en portant sa propre tête, le trajet jusqu'à l'actuel emplacement de la basilique, au Nord de Paris, où il aurait été enseveli. Une abbatiale y fut érigée à l'époque mérovingienne.
Au XIIe siècle, sous l'impulsion de l'Abbé Suger, l'église fut reconstruite et agrandie. De style gothique, l'actuelle basilique présente des éléments de style roman sur sa façade. L'église fut fortement endommagée sous la Révolution Française. En 1847, la flèche Nord menaçant de s'effondrer, elle fut démontée. Un projet de reconstruction de cette flèche, avec les pierres d'origine, a été lancé en 2016.
Dès son origine, l'église fit fonction de nécropole royale et la plupart des rois de France, de Dagobert Ier à Louis XVIII, y sont inhumés. Depuis 1996, la Basilique Saint-Denis est la cathédrale du Diocèse de Saint-Denis.