Aucune documentation se rapportant à l'église paroissiale Notre-Dame de Coyolles ne semble avoir été conservée avant le 19e siècle, et les profondes restaurations entreprises en 1874-1875 ne facilitent pas l'analyse du monument.

Selon l'historien soissonnais Bernard Ancien, cité par de nombreux auteurs dont Alain Jacono, l'église aurait été construite au 11e siècle, édifice dont il subsisterait au moins les murs du chœur et le clocher qui le surmonte. Il propose d'imaginer pour cette époque une église dont la nef aurait été encadrée par deux collatéraux symétriques s'achevant en absidiole de part et d'autre du chœur.

Si rien n'étaie plusieurs composantes de cette hypothèse, l'église de Coyolles n'en a pas moins possédé jadis un collatéral nord - depuis longtemps disparu - comme le suggèrent les arcades en plein cintre, bouchées, qui se succèdent le long du mur nord de la nef. Cette nef profite d'une réédification (ou de transformations) vers le milieu du 12e siècle, attestée par la forme et le décor encore "romans" du portail occidental. Ces travaux sont suivis au tout début du 13e siècle par la reconstruction du collatéral sud, accompagnée de l'élévation de sa chapelle consacrée à la Vierge. Le style des chapiteaux des arcades qui relient la nef et son collatéral correspond en effet à cette époque, en espérant que ces chapiteaux n'aient pas été trop modifiés lors de la restauration de 1874-1875. La Renaissance semble être peu intervenue dans cet édifice et ne lui avoir apporté que sa tourelle d'escalier hors-œuvre et l'ouverture ou l'agrandissement de la baie qui ajoure le mur oriental du sanctuaire. Aucune autre intervention ne peut être détectée, si ce n'est le rajout d'une sacristie à l'est de la chapelle de la Vierge, dans le courant du 17e ou du 18e siècle. Un document d'époque révolutionnaire, transcrit par Alain Jacono, signale que la fausse-voûte de la nef est alors lambrissée.

Au début du 19e siècle, malgré le passage de la Révolution, l'église paraît en bon état et ne nécessite que quelques travaux d'entretien. Pourtant, vers le milieu du siècle, l'édifice exige alors d'importantes réparations. L'adjonction de la sacristie à l'arrière de la chapelle de la Vierge a gravement compromis la solidité de cette partie du monument. En effet, sa construction a provoqué la suppression de contreforts, ainsi que le percement du mur de la chapelle pour ménager une porte de communication. En outre, cette sacristie, construite en mauvais matériaux, est basse et d'un accès difficile. Dans un rapport daté du 16 septembre 1873 et conservé dans les archives communales, l'architecte soissonnais Casimir Truchy propose de la détruire et d'en établir une nouvelle dans une pièce de l'ancien presbytère attenant à l'église et qui sert d'école depuis 1833. Diverses mesures de conservation et d'amélioration sont aussi préconisées : les piliers doivent être repris, plusieurs contreforts renforcés et surtout, le clocher doit être chaîné. Il faut également repiquer les murs, agrandir les fenêtres de la nef et refaire le dallage en mauvais état de l'église, cette dernière opération devant permettre de sauver plusieurs dalles funéraires qui seront levées et placées contre les murs. Au cours de cette campagne de travaux menée en 1874-1875, la chapelle de la Vierge est presque entièrement rebâtie sous la direction de Casimir Truchy, grâce aux libéralités d'Henriette-Adèle Moreau-Daudin - propriétaire du château voisin -, qui finance également la restauration de l'église. Cette réfection satisfait à un souhait que son époux, Auguste-Ferdinand-Louis Moreau, a exprimé avant sa mort (d'après l'inventaire après décès et le partage de la succession d'Auguste-Ferdinand-Louis Moreau). Une plaque de cuivre gravée, fixée dans la chapelle, pérennise le souvenir de ces travaux.

Le cimetière paroissial, qui entourait l'église à l'est et au sud, est transféré vers 1842, pour des raisons de salubrité. Son emplacement primitif est transformé en square et place publique en 1878, grâce à la générosité d'Eugène Favard, maire de Coyolles et membre de la famille Moreau (d'après une plaque insérée dans la maçonnerie du monument).

L'édifice traverse la Première Guerre mondiale sans subir de dégâts importants. La réfection de la couverture de l'église en 1997 a été subventionnée par la Sauvegarde de l'Art français.