L'église Notre-Dame de Gajan est érigée à la fin du XVIIe siècle mais est incendiée par les Camisards en 1703. Selon la monographie du diocèse de Nîmes écrite par l’abbé Goiffon l’édifice aurait été reconstruit dans la seconde moitié du XIXe siècle. Cette affirmation correspond sans doute davantage aux restaurations entreprises au milieu du XIXe siècle mentionnées dans les archives.

Dès 1855, en raison de l'éloignement de la paroisse de Fons, les catholiques demandent à la commune un soutien pour restaurer l'église de Gajan en vue de l'ériger en succursale. Malgré le soutien de la municipalité de Fons, la commune de Gajan émet un avis défavorable au projet. Une souscription volontaire est alors organisée en 1859 : 903 francs sont récoltés. Un premier projet, présenté par l’agent-voyer cantonal Adrien Gory prévoit en 1861 une reconstruction de la façade et des voûtes pour 3 000 francs. Même si ce projet n’est pas retenu par le conseil de Fabrique, on observe de fortes similitudes entre la façade actuelle et celle projetée.

Le rapport de l’architecte Henri Durand, inspecteur des édifices diocésains, du 16 avril 1866 entraîne l’interdiction du culte dans cette église. Il met en avant sa vétusté, le risque d’effondrement de la toiture et le manque de solidité des matériaux employés pour les contreforts (pierre sèche). Ces problèmes structurels sont sans doute dus à la proximité de la ligne de chemin de fer de Beaucaire à La Grand-Combe ouverte en 1841. Les restaurations prévues (environ 2000 francs) sont la reconstruction de la façade et de la couverture, du clocher et la consolidation des contreforts au mortier de chaux.

L’évêque de Nîmes, craignant la dégradation des textiles en raison de l’humidité du bâtiment, confirme l’urgence de ces travaux dans une lettre écrite au préfet le 23 octobre 1866. Le département et la commune soutiennent cette restauration en apportant respectivement des subventions de 300 et 800 francs. Le chantier est confié au maître-maçon Pierre César le 25 mars 1867. L'église est bénie par l’évêque Plantier le 9 octobre suivant. En 1994, la sacristie est consolidée puis en 2005 la verrière représentant la Vierge, par Rose May Prévost, est installée dans la baie anciennement murée du choeur.