En la tarde del 1 de abril de 1940, después del segundo desfile de la victoria por las calles de Madrid y un almuerzo de gala en el Palacio Real, Franco se desplaza a Cuelgamuros junto a su esposa, altos cargos de su Gobierno y del ejército, autoridades de Movimiento, responsables de la Sección Femenina y los embajadores de Alemania, Italia y Portugal. En la base del Risco de la Nava, el coronel Valentín Galarza, secretario de la Jefatura de Estado, lee en voz alta el Decreto; posteriormente, se detona el primer barreno. Se pone así en marcha una obra que durará casi diecinueve años, movilizando unos recursos ingentes en un contexto de pobreza y miseria general en la posguerra.
En un primer momento, se ocupa de la obra el arquitecto Pedro Muguruza, Director General de Arquitectura, autor de los primeros bocetos y diseños de la cripta del monumento. En julio de 1941 se crea el Consejo de las Obras del Monumento Nacional a los Caídos, presidido por Valentín Galarza, que era entonces ministro de la Gobernación, cuya misión era “realizar los proyectos aprobados en el mínimo plazo posible, proveyendo las soluciones de los problemas que pudieran surgir en la ejecución de las obras”.
La ejecución de la obra fue adjudicada por concurso a tres grandes contratas: la perforación de la cripta la llevaría a cabo la empresa San Román; el monasterio y edificios aledaños fueron encomendados a la empresa Molán; y la carretera de acceso fue construida por la empresa Banús. Cada una de las empresas pone en marcha y gestiona un destacamento específico, en los que hay tanto trabajadores libres como mano de obra penada. La magnitud de la obra y la lentitud en su avance hace que el régimen active el mecanismo de la redención de penas por trabajo, teorizado por el jesuita José Agustín Pérez del Pulgar.
En enero de 1942 llegó al Valle una compañía del 95 batallón de soldados trabajadores penados. Entre 1943 y 1950 miles de presos políticos trabajaron en el Valle. El uso de presos políticos en la obra, los beneficios que pudieron reportar a las empresas contratistas y la magnitud de los accidentes laborales o las enfermedades asociadas a la precariedad de las condiciones de trabajo han figurado durante las últimas décadas entre los aspectos más controvertidos de la construcción del monumento.
En 2021, una prospección arqueológica en los destacamentos penales, especialmente en el de Banús, sacó a la luz las condiciones de vida de los trabajadores libres y presos, y también las de los familiares que les acompañaron, que habitaron en conjuntos de chabolas en torno a los destacamentos desde 1947.
En 1950, el arquitecto Diego Méndez sustituye a Pedro Muguruza en la dirección de las obras, lo que supone cambios relevantes en su escala y planificación. El conjunto escultórico del exterior -que incluye una escultura de la Piedad, situada sobre la puerta de entrada, así como las de los cuatro evangelistas y las cuatro virtudes cardinales, en la base de la cruz- es obra de Juan de Ávalos, así como los cuatro arcángeles situados en el crucero de la basílica. La cruz que corona el Valle, de 150 metros de altura, es un diseño de Diego Méndez.
Aunque domina la simbología religiosa, el conjunto presenta en su programa iconográfico un marcado carácter militarista, expresado en los arcángeles vigilantes del atrio, armados con espadas; las seis capillas laterales, dedicadas a patronas de las fuerzas armadas o hechos militares o imperiales; las alegorías de las fuerzas armadas situadas a ambos lados del último tramo de la nave, o las escenas de batalla situadas en la parte inferior derecha de la cúpula, que incluyen la presencia de un carro de combate, combatientes, y banderas de las facciones vencedoras en la guerra.