Située au cœur du domaine royal, l'église de Montagny est citée pour la première fois au XIIe siècle et plus précisément en 1154 quand Thibauld, évêque de Senlis, la remet avec les terres et les droits qui s'y rattachent à l'abbaye royale Saint -Vincent de Senlis . Une communauté de chanoines envoyée par l'abbaye fonde rapidement un prieuré dont les bâtiments sont construits contre le flanc nord de l'église.
Le prieuré qui assure également les fonctions paroissiales du village prospère. Durant le XIIIe siècle, les chanoines entreprennent des travaux dans l'église , en témoignent certains supports du chœur qui d'après les récentes recherches datent de cette période.
L'église, sous la Révolution ne subit pas de destructions majeures. En 1791, les bâtiments de l'ancien prieuré sont vendus à un agriculteur par les administrateurs du Directoire du district de Crépy. En 1792, l'église est utilisée pour les élections municipales et pour les réunions du Conseil. En 1794, elle devient Temple de la Raison : on retire le coq et les croix.
Les premières années du XVIe siècle voient la construction de l'église actuelle. Celle-ci est bâtie sur les fondations de l'ancien édifice. Certains supports du chœur datant du XIIIe siècle sont cependant conservés lors de cette campagne de travaux qui se déroule durant les années 1510-1515. Le portail est remplacé au milieu du siècle vers 1540, et la similitude entre ses fleurons sculptés et les fleurs peintes de l'abside suggère que ce décor ait été réalisé à la même période. Quelques années plus tard, le retable racontant le martyr de sainte Félicité et de ses sept enfants est placé dans l'église. Les dimensions du retable similaires aux dimensions de l'abside suggèrent qu'il ait été spécialement réalisé pour occuper l'endroit en étant déposé sur l'autel en pierre.
A la fin du siècle, probablement pour des raisons d'effectif et d'économie, la communauté de chanoines quitte Montagny. Seul un prêtre, chanoine de saint-Augustin, doit desservir la paroisse. Les anciens bâtiments du prieuré sont alors loués à des laboureurs. La nouvelle église est consacrée en 1624, par un autre évêque de Senlis, Nicolas Sanguin. A la demande des paroissiens, sont apportés de Rome, en 1783, les reliques de sainte Félicité. Celles-ci sont déposées dans une châsse en bois dont la réplique, réalisée après la première guerre mondiale, sert aujourd'hui de reliquaire.
XIXe siècle
Beaucoup de travaux sont effectués en raison de l'état déplorable de l'édifice, essentiellement sur la flèche et sur la toiture. En 1862, l'église est classée aux Monuments Historiques. A la fin du siècle, des vitraux, tous offerts par des habitants du village - dont ils portent la dédicace - sont installés dans l'édifice.
XXe siècle
De nombreux travaux sont encore entrepris sur l'édifice : les abats-sons sont remplacés, ainsi que la toiture. Fait notable, deux de nos statues, une Pièta et un saint Sébastien rejoignent le musée d'art sacrée de Crépy en Valois en 1973 suite à la grande exposition "Trésors du Valois ".
En 1984 a lieu la restauration du coq. Durant la décennie 1990, se multiplient les opérations relatives à la sauvegarde de l'église : 1996, sauvetage des peintures de l'abside ; étude réalisée sur l'état de la bâtisse, étude de faisabilité réalisée sur le retable de sainte Félicité. Le site est aussi retenu pour la réalisation de films publicitaires et pour le cinéma.