En 1959, le diocèse fait l’acquisition d’un terrain situé à la jonction du quartier des Brichères, en cours de construction, et de la Zone à Urbaniser en Priorité (ZUP) qui est encore à l’état de projet. Tandis que la construction du presbytère et des salles de catéchisme démarre en 1961, la pose de la première pierre de l'église n’a lieu que le 23 octobre 1966. Entre temps, un nouveau projet a été élaboré par l’architecte Pierre Prunet retenu pour cette opération. Ce délai et l’évolution du projet traduisent les difficultés que l’association des Amis des nouvelles églises d’Auxerre rencontre pour financer les salles paroissiales et les lieux de culte dans les nouveaux quartiers de la ville. Néanmoins, les deux projets prennent une forme similaire. Le plan massé circulaire prévu en 1959, devient décagonal en 1966. Le clocher, isolé dans les deux projets, reproduit la silhouette de l’église. L’évolution la plus visible réside dans la forme de la toiture rappelant celle d’une tente.  L’architecte utilise abondamment la brique de qualité Vaugirard pour le parement des murs, à l'extérieur comme à l'intérieur. Les travaux sont confiés à l'entreprise Picarat pour le gros œuvre, Villard et Garrigues pour la charpente et la couverture, Nicolardot pour la menuiserie, Favergat frères pour la plomberie, Jussot et fils pour l'électricité et le chauffage, enfin, les entreprises Arri (Toucy) et Schiffer s’occupent respectivement de la serrurerie - miroiterie et de la peinture. Jean Quillot (Auxerre) réalise les menuiseries en chêne de l'église et du centre paroissial. Pendant sa conception, l’église connaît plusieurs vocables successifs : appelée tout d’abord Notre-Dame de Lourdes en raison du centenaire de l’apparition de la Vierge dans la grotte, elle devient Notre-Dame des Brichères. C’est à Sainte-Geneviève qu’elle est finalement dédiée, lorsqu’en en 1969 l’archevêque Stourm la consacre. En 1970, son lanternon fourni par l'entreprise Saint-Gobain est installé. Le clocher, l’isolation et le couvrement n’ont pas été réalisés. Les matériaux détaillés par l’architecte dans le projet ont parfois été remplacé par d’autres moins onéreux. A l’intérieur, la chapelle des fonts et la chapelle de semaine (ou comportant le Saint-Sacrement) n’ont pas été créées. Plus tardivement, une chapelle de semaine et une salle de réunion ont été aménagées de part et d’autre de la sacristie, avec la pose de parois vitrées, afin de clore les deux espaces. La sacristie est devenue un oratoire, tandis que le bureau attenant reprend la fonction de sacristie. Les portes en verre de l'entrée principale de l'église ont été remplacées par des portes en bois, réalisées par un paroissien (M. Dumont).