El 1 de noviembre de 1.966, solemnidad de Todos los Santos, el arzobispo diocesano, D. Segundo García de Sierra y Méndez, bendecía la primera piedra de un complejo parroquial, en el que se contemplaba la edificación de una iglesia, un colegio anejo a ella y un patio de recreo. Un año después, concretamente el 19 de noviembre de 1.967, se erigía la nueva parroquia, y se dedicaba a NUESTRA SEÑORA DE FÁTIMA. La razón de esta dedicación mariana venía motivada por estar celebrándose en esos momentos el 50º aniversario de las apariciones de la Virgen María en Fátima a Lucía, Francisco y Jacinta.
Los terrenos en los que fueron edificados la iglesia y el colegio parroquial habían sido donados al arzobispado por D. Ramón Sanahuja Boch, propietario también de la empresa que había construido las llamadas “Mil Viviendas” (hoy: “Barriada Juan XXIII). El proyecto de la iglesia y colegio se encargó al arquitecto Manuel SÁNCHEZ ARROYO; pero al morir inesperadamente en accidente de tráfico, se hizo cargo de la obra el arquitecto Angel ESTEVE JAQUOTOT, quien presentó un nuevo proyecto para la iglesia.
Fue consagrada solemnemente el 9 de mayo de 1.971. Es la primera parroquia que surge en el Barrio de Gamonal, después de la integración del antiguo pueblo en el Ayuntamiento de Burgos (1 de enero de 1.955). Su feligresía sobrepasa las 11.000 personas.