Having already overseen the construction of Les Halles, Louis VI ordered the construction of the church and cemetery in 1130. The Saints-Innocents' cemetery became the cemetery for all the churches in Paris, leading to an unprecedented concentration of corpses, especially due to the fact that a plague epidemic could cause thousands of deaths in the span of a few weeks.
Improvements to the cemetery were made in the 15th century, partly funded and designed by the alchemist Nicolas Flamel. A macabre mural depicting the Dance of Death was also painted at the southern side of the cemetery. In 1527, the Assassin Giovanni Borgia and his traveling companion, Maria Amiel, visited the cemetery to discover whether or not Nicolas Flamel and his wife, Perenelle, had achieved immortality by creating the elixir of life. After opening Nicolas and Perenelle's coffins, they were shocked to find them empty.
Just before the outbreak of the French Revolution, the bodies at the cemetery were disinterred and moved to the Parisian catacombs. In March 1791, the conservative Templar Chrétien Lafrenière held a rally at the cemetery with his followers and loyal Templars from around Europe. In preparation, guards were posted around the area, and the gravediggers were taken prisoner after resisting Lafrenière's plans. At the same time, the Assassin Arno Dorian infiltrated the cemetery with the intent to kill Lafrenière, having been manipulated by the Grand Master of the radical Templars, François-Thomas Germain.
At the rally, Lafrenière criticized the radical Templars who had supported the Jacobins and the Revolution. As he and his men prepared to attack the radical Templars at the Hôtel de Beauvais, Lafrenière was assassinated by Arno. The latter later returned to the cemetery with a team of Assassins to track down Didier Paton, a spy that they had rescued from execution.