Les plans de l'église et sa construction furent initialement confiés à Jean-Baptiste Lepère, architecte de renom de l'époque. La première pierre fut posée en août 1824 en présence du préfet de la Seine Gaspard de Chabrol et de l'archevêque de Paris M de Quélen. Les travaux furent menés avec une certaine lenteur puis ponctuellement abandonnés, un manque de crédit puis surtout la révolution de 1830 retardant le projet... C'est donc son gendre, Jacques Hittorff, qui la poursuivit en 1831 jusqu'en 1844 où elle fut livrée au culte le 25 octobre. Il modifia énormément le projet initial (les premiers projets de l'église ne faisaient état que d'un seul clocher), ouvrant la place Franz-Liszt sur l'église. La place devenait ainsi une sorte de parvis pour celle-ci. Il ajouta de plus un système de rampes, aménagé aujourd'hui en jardins, destiné à faciliter l'accès des calèches.
De plan basilical, elle évoque toutes les grandes réalisations de l'architecture religieuse sans en copier aucune. Au-dessus du portique, emprunté aux temples grecs, le fronton sculpté par Charles-François Lebœuf-Nanteuil a pour sujet L'Apothéose de saint Vincent-de-Paul - le saint est glorifié, entouré de figures symbolisant son action : un missionnaire, un galérien, des Filles de la Charité se dévouant à des enfants ou à des malades. À l'intérieur, la frise peinte de 1848 à 1853 par Hippolyte Flandrin autour de la nef, entre les deux étages de colonnes, représente cent soixante saints et saintes s'avançant vers le sanctuaire. Le plafond de la nef a été réalisé par le sculpteur Luglien François Badou. Le décor de la chapelle de la Vierge, au chevet, une adjonction postérieure, est de William Bouguereau (1885-1889). Le calvaire du maître-autel est de François Rude.
Défenseur d'une architecture polychrome, Hittorff avait fait couvrir une grande partie de la façade, derrière la colonnade, de plaques de lave émaillée peintes par Jules Jollivet. Malheureusement, la nudité de certains personnages provoqua un tel scandale qu'on dut ôter toutes les plaques en 1861. Une plaque de lave a été remise en place en octobre 2009, deux sont accrochées à l'intérieur de l'église.
Cette église a souffert de la Commune, ses clochetons reçurent sept obus et son perron, plus de vingt, tous tirés du Père-Lachaise.
