La iglesia, emplazada en la ladera este del cerro del Castillo, en la confluencia de las calles de San Esteban, Valentín Palencia y el Pozo Seco, y dando nombre al barrio, se empezó a construir en el último cuarto del siglo XIII, bajo el reinado de Alfonso X El Sabio, continuando su proceso durante las primeras décadas de la siguiente centuria.