La ciudad de Cuenca fue reconquistada por el Rey Alfonso VIII de Castilla en el año 1177. Desde entonces comenzaron a construirse las principales parroquias de la ciudad. Se edificarán catorce, todas ellas dentro del recinto amurallado que se encuentra entre los márgenes de los ríos Jucar y Huercar.
Entre estas parroquias se encuentra la de San Esteban Protomártir, construida dentro del recinto amurallado y cerca de la Puerta de Valencia. Se desconoce la fecha exacta de su construcción y es uno de los edificios más enigmáticos de la ciudad, pues hoy nada queda del primitivo templo. De hecho la Parrroquia de San Esteban ha tenido su sede en, al menos, cuatro ubicaciones distintas.
Vicente Busquet, Cura propio de San Esteban Protomártir, escribía en el libro XV de Bautismos de la Parroquia: " En el día 22 de noviembre de 1852 se celebró la primera misa en la Iglesia de San Francisco, como Parroquia de San Esteban". Y sigue la nota diciendo: "Se trasladó, por deterioro de la Iglesia anterior de San Esteban Protomártir situada dentro de la muralla (frente a la ermita del Stmo. Cristo del Amparo y de Santa Catalína del Monte Sinaí), en la Calle de Santa Lucía, y tuvo como motivo el crecimiento de la ciudad y la belleza del Convento de los Franciscanos."
El Convento Franciscano al que se refiere, se encontraba situado en el solar que actualmente ocupa el nuevo edificio de la Parroquia de San Esteban. La Fundacion de este convento se remonta al siglo XIV. La desamortizacion que la Iglesia sufrio en el siglo XIX hizo que desapareciesen primero los frailes y despues las huerta y el convento. Solo sobrevivio la Iglesia, donde se trasladó en el año 1852 la sede de la Parroquia de San Esteban. En el año 1961 se procedio al hundimiento de la Iglesia del Convento con el fin de edificar un nuevo edificio para la Parroquia de San Esteban. Mientras se llevaban a cabo las obras de construccion del nuevo templo, el culto de la Parroquia se trasladó a la antigua Zona de Reclutamiento.
En el año 1959 se había convocado un concurso para elegir el proyecto de la nueva Iglesia. El 10 de mayo de 1960 se produjo el fallo del Concurso, aunque sin faltar polémica. Se eligio el proyecto del Arquitecto Antonio Camuñas Paredes. Comenzaron así diez años de obras.
El dia 21 de marzo de 1970, víspera del Domingo de Ramos, el entonces Obispo de Cuenca, Mons. Inocencio Rodriguez, dedicaba el nuevo templo, de lineas agresivas y angulares, siendo cura ecónomo D. Manuel Cañas Soria. Del nuevo templo llaman también poderosamente la atencion las vidrieras, obra del artista Rafael H. de Caviedes.