Le culte de Saint Paterne est introduit à Orléans par des Bretons, fuyant les invasions Normandes du Xème siècle. L'église était autrefois appelée Saint-Pouair. Jusqu'à la Révolution, il s'agissait d'un prieuré rattaché à l'abbaye Saint-Père de Chartres, dont un document de 1115 fait mention.
Saint-Paterne ne se trouvera à l'abri des remparts qu'après la construction de la dernière enceinte entre 1485 et 1555. C'est pourquoi au cours de la guerre de cent ans, elle sera détruite 2 fois par les orléanais eux-mêmes (en 1358 et 1428), redoutant que les anglais n'utilisent le bâtiment comme place forte.
L'église est reconstruite au début du XVIème siècle, et on lui adjoint une tour de brique qui sera surmontée d'un dôme en pierre de taille, tel que celui des églises St-Euverte, Saint-Laurent ou Saint-Paul.
En 1562, les Huguenots décapitent la tour, puis en 1567, démolissent l'église. En 1588, c'est au tour des Ligueurs d'investir la paroisse. Pour venger l'assassinat du duc de Guise et de son frère, un autre frère, le duc de Mayenne, résidant à Orléans, soulève les habitants contre l'autorité royale. Le gouverneur Balzac d'Entragues, resté fidèle au roi, s'enferme dans la citadelle de la porte Bannier. Mayenne fait alors enlever la toiture à peine restaurée et combler la nef avec de la terre et des gravats pour constituer une plateforme d'artillerie destinée à bombarder la citadelle. Le 31 janvier 1589, Balzac se replie à Beaugency.
Après les guerres de religion, l'église est remise en état, moyennant d'importants travaux.
En 1771, un sanctuaire est aménagé vers l'est. Le prieuré est supprimé à la Révolution, mais la paroisse est maintenue jusqu'en 1793. En 1795, l'église est rendue au culte, mais comme toutes les autres, elle est rebaptisée pour porter le nom d'une fête civique qui doit s'y dérouler : c'est ainsi que Saint-Paterne devient le "temple des vieillards" jusqu'au Consulat.
En 1812 une petite chapelle de la Sainte-Vierge est construite dans le bas-côté nord.
En 1870, devant l'état déplorable du bâtiment et le nombre important de fidèles, l'abbé Chesse, curé de la paroisse, commence sérieusement à envisager l'édification d'une nouvelle église. La décision définitive sera prise en 1874, et le 9 mai 1876, Mgr Dupanloup pose la première pierre. En 1883, le choeur, les chapelles, le transept et la sacristie sont terminés, et l'église, inaugurée par Mgr Coullié, commence à être utilisée. En 1888 c'est le démarrage de la construction de la nef. Les travaux, momentanément interrompus par manque d'argent, sont repris en 1892, et définitivement terminés en 1894. Le 11 décembre de cette même année, la nouvelle église est consacrée solennellement par Mgr Touchet.
La vieille tour en très mauvais état est alors le seul vestige qui reste de l'ancienne construction. Le maire Ferdinand Rabier fait voter sa démolition en 1913 malgré une vive opposition.
Le 7 mai 1931 Mrg Courcoux, bénit le nouveau portail occidental.
