Entre los siglos XIII y XIV los colonos segovianos de estas tierras construyeron una humilde y sencilla iglesia junto a una antigua torre árabe de vigilancia (construida entre el 852 al 866 por el Emir Muhammad de Córdoba) y la pusieron bajo la advocación de Santa Catalina Mártir y Virgen.
Un informe eclesial de 1671 ya califica el templo de muy antiguo, aunque en 1601 se le habían realizado algunas reparaciones.
A la iglesia se la describe en algunos escritos de la siguiente forma: «adosada a un torreón de vigilancia una pequeña iglesia de tres naves separadas por pilares que sustentan arcos apuntados. La cubierta, de teja a dos aguas, sobre entramado de madera. La capilla mayor, donde el hidalgo Gómez de Haro, probablemente se encontrara en un ábside». Un documento de 1670 nos dice lo siguiente: “a la parte de oriente en la capilla mayor donde está el arco antiguo”. Este arco marcaría la transición entre el cuerpo principal y el hipotético ábside donde estaría la capilla mayor.
La primera reforma importante de la que tenemos constancia documental tuvo lugar a finales del siglo XVII. El encargado de realizar la obra fue D. Santiago Sopeña vecino de Alcalá de Henares. Se realizaron diversas reparaciones en los muros, cubierta, capilla mayor, etc. Pero lo verdaderamente importante consistió en el derribo del viejo torreón y en la construcción de una torre campanario, prácticamente la misma que ha llegado hasta nuestros días.
Las gestiones ante el Obispado de Toledo se debieron iniciar en 1670 y las obras estaban terminadas en 1688 cuando Eugenio Montero y Leandro Morales, alcaldes ordinarios de Majadahonda, realizaron el último pago de obras al alcalaíno.
En 1726, D. Pedro Hernández, maestro de obras presentó el proyecto y las condiciones en las que había de realizarse la reforma en la iglesia parroquial. Se trataba de la construcción de un nuevo presbiterio de planta octogonal, que amplía el edificio y viene a sustituir la antigua capilla mayor, adosado al preexistente cuerpo de tres naves. Las obras las realizará Nicolás Díaz, maestro albañil, vecino de Villaluenga. Se comenzaron muy pronto pues en 1727 ya se estaban realizando. Se terminan en 1731.
Además, unos años después, se construye una sacristía con un cuarto anejo y una barbacana para proteger el edificio dada la pendiente que existe en el lugar en el que está emplazada la iglesia.
Gracias a unos planos de 1870, podemos contemplar la planta del templo en su totalidad, muy similar a la actual. Es un edificio de planta rectangular de 33x14x20m de alto en el campanario. En el interior tres naves separadas por pilares sobre los que descansan arcos apuntados, el campanario del siglo XVII y el presbiterio del siglo XVIII.
Cuando terminó la guerra, la Dirección General de Regiones Devastadas acometió la reconstrucción y restauración de Majadahonda y de la parroquia. Los arquitectos decidieron conservar los muros que quedaban de la iglesia. Sobre las ruinas construyeron el templo que conocemos siendo muy parecido al anterior a la guerra.
La reconstrucción se redujo a dar mayor altura al edificio, elevando su cubierta, estilizando el capitel y la linterna, dando mayor altura a la torre.
El primer proyecto e informe de restauración se realiza en 1940 por el arquitecto D. Víctor Calvo Martínez de Azcoitia. El segundo en 1944 por D. Juan Armado González de la Puente y el tercero en 1949 por D. Félix Ugalde Rodrigo quien termina las obras entre los años 1953-54.
La restauración supuso algunos cambios en el edificio:
- En la fachada oeste, la torre conserva la planta pero aumenta en altura realzando su silueta con un chapitel cuya veleta desde el comienzo quedo torcida. A su lado se trasladó el antiguo pórtico, que da entrada a la iglesia por debajo del coro, con las columnas antiguas y tejado a tres aguas.
- El cuerpo principal, con entrada sotocoro conserva sus muros que fueron reforzados. Dos filas de pilares mantienen la división de tres naves y los antiguos arcos apuntados son sustituidos por otros de medio punto. La cubierta es a dos aguas con teja árabe sobre cerchas vistas en el interior.
- El presbiterio más elevado que el resto del edificio, mantiene la planta octogonal y una cúpula que descansa sobre arcos de medio punto con una linterna y cubierta octogonal de pizarra.
- Se enfoscan todos los paramentos exteriores tapándose la antigua estructura de adobe y piedra. Se adosa al cuerpo principal dos cuerpos cubiertos a un agua. En la fachada que da a la plaza se construyó una logia con arcos de medio punto, característica de la reconstrucción de Regiones Devastadas, que sirve de acceso lateral a la iglesia.
- En la fachada meridional, la sacristía y las dependencias parroquiales se ampliarán en los años sesenta.
En el verano de 2021 se repararon diversos desperfectos y se restauró la pintura del templo