Como la mayor parte de las iglesias románicas de Segovia, fue construida entre los siglos XII y XIII.

Fue propuesta para su demolición en 1859 junto con otras iglesias como San Quirce, San Román y San Facundo por Francisco Verea.^[1]​

En 1881 siendo propiedad de Pedro Romero, la ya ex-iglesia fue derribada, con objeto de «mejorar el ornato y comodidad del [vecino] Palacio de la Corporación Provincial».^[2]​ Parte de sus piedras se usaron para construir la bajada de la Canaleja.^[3]​

Se trataba de una iglesia de una sola nave, de estilo románico. Contaba con un ábside sencillo orientado al sudeste. Al sur del ábside se erguía la torre de planta cuadrada que sobresalía la altura de la iglesia y se remataba con un cuerpo con dos arcos por cada lado. La torre se coronaba con un chapitel de pizarra. La iglesia aparece descrita en Las calles de Segovia (1918) de Mariano Sáez y Romero, en el epígrafe dedicado a la plaza a la que dio nombre, con las siguientes palabras:^[4]​

Antiguamente se llamaba de San Pablo, por tener en su lado occidental la iglesia de este nombre, derribada hace unos cuarenta años. Era un templo muy pequeño, de graciosa portada bizantina, un ábside liso con labrada ventana, torre alta con arcos de ladrillo. Su capilla mayor perteneció a la casa de Contreras. En el sitio que ocupaba hay ahora un diminuto y bien cuidado jardín.

(Sáez y Romero, 1918, p. 42)

1. ↑ «Segovia». Románico Digital (Fundación Santa María la Real). 
2. ↑ Ruiz Hernando, José Antonio (1982). Historia del Urbanismo en la ciudad de Segovia del siglo XII al siglo XIX. 1 y 2. E.T.S. Arquitectura (UPM). p. 57. ISBN 978-84-500-5403-3. Consultado el 28 de marzo de 2023. 
3. ↑ Redacción (25 de octubre de 2018). «J. M. Martín Sánchez, Las piedras de la iglesia de San Pablo a la Canaleja | El Adelantado de Segovia». Consultado el 28 de marzo de 2023. 
4. ↑ Sáez y Romero, 1918, p. 42.

• Peñas, Pedro Luis (1 de junio de 2013). «La iglesia de San Pablo de Segovia antes de 1881». Segovia y Matemáticas. Consultado el 28 de marzo de 2023. 
• Sáez y Romero, Mariano (1918). «Conde de Cheste (Plazuela de)». Las calles de Segovia. Segovia: Antonio San Martín. pp. 42-44. Wikidata Q32192602.