Las primeras noticias documentales que se tienen de un edificio religioso con la advocación de San Pedro ad vincula (encadenado) que constituiría el centro de la antigua Villa de Vallecas -absorbida por Madrid en 1950- datan de 1427, cuando se indica que existía una iglesia mudéjar de pequeñas dimensiones con muros de mampostería de pedernal, ampliándose los datos en 1547, cuando se describe como un templo de tres naves dos altares y un altar mayor. Las excavaciones arqueológicas realizadas durante la restauración de 2012-2015 han confirmado que este templo del siglo XVI tendría dimensiones similares al templo actual, con el cuerpo de naves –más ancha la central- cubierto por estructura de madera, y el crucero y la cabecera poligonal por bóvedas estrelladas según modelos tardogóticos de Rodrigo Gil de Hontañón. Cuando Felipe II traslada la Corte a Madrid en 1561, Vallecas comienza a multiplicar su población gracias a su cercanía y a estar situada en el camino a Valencia, lo que provoca que sea necesario la construcción de un lugar de culto de mayores dimensiones. Como resultado, la iglesia no responde a un proyecto único sino que es consecuencia de sucesivas etapas constructivas: a principios del siglo XVII el anterior templo de tres naves se divide en cuatro tramos, que se refuerzan con contrafuertes y se abovedan, con cañón rebajado con lunetos termales la nave central y con bóvedas de arista las laterales; el crucero gótico se amplía a ambos costados para formar el transepto; y la cabecera poligonal se sustituye por una cuadrangular cubierta con bóveda de medio cañón con lunetos, unificándose el conjunto con una articulación de pilastras y entablamentos dóricos de tradición herreriana que preludian modelos barrocos madrileños, aunque conservando la nota anacrónica de la espléndida bóveda estrellada del crucero. Tras muchas dilaciones, esta cabecera acogió desde 1669 un retablo mayor realizado por Pedro y Francisco de la Torre sobre un pedestal marmóreo ejecutado por Bartolomé Sombigo, que estaba adornado con esculturas de Pedro Alonso de los Ríos y Juan Sánchez Barba y pinturas de Francisco Rizi, que terminó el gran lienzo central de La liberación de San Pedro por el ángel en 1670. Simultáneamente la iglesia adquiere una apariencia barroca a través de la decoración, los retablos y la construcción de capillas a su alrededor: tres grandes y complejas abiertas a la nave del Evangelio en el siglo XVII, y dos pequeñas a modo de hornacinas abiertas a la de la Epístola en el XVIII. Además en la primera mitad del siglo XVII se construye junto al muro sur de la cabecera una capilla-camarín de Nuestra Señora del Rosario, decorada con importantes pinturas murales atribuidas en parte a Juan Vicente de Ribera; mientras que al norte se levantan la sacristía y salones parroquiales.
El exterior del templo está construido en aparejo toledano -verdugadas de ladrillo que enmarcan cajeado de mampostería- reservando la piedra de granito para vanos y portadas. Finalizada antes de 1630, la fachada principal a los pies es de traza sencilla, y se remata por un frontón mixtilíneo coronado por grandes jarrones en cuyo tímpano se abre un gran óculo bajo un relieve con los atributos de San Pedro. La portada de acceso, atribuida al arquitecto Gaspar Ordóñez, está compuesta por un vano de medio punto flanqueado por columnas pareadas exentas sobre plintos, que sustentan un frontón curvo partido coronado por pináculos, con una hornacina en su centro flanqueada por pilastras dobles y rematada en frontón triangular, que acoge un bajorrelieve barroco de La liberación de San Pedro. En el lateral izquierdo de la fachada se eleva una alta torre de tres cuerpos: el inferior construido en aparejo toledano; el segundo, que alberga las campanas, en ladrillo, ambos de planta cuadrangular del siglo XVI; y el tercer cuerpo de planta ochavada con vanos adintelados rematado por un chapitel de pizarra, añadido en siglo XVIII, sin que pueda afirmarse con certeza ser obra de Ventura Rodríguez, aunque se sabe que intervino en la torre en 1775; pues en esa época se emprenden diversas obras de modernización, como la creación de una nueva portada neoclásica de acceso “llamada de el Sol” por el costado sur, que trazó en 1776 Manuel Machuca Vargas, o la reforma del presbiterio, actualizando el retablo mayor “quitándole la mala talla, y adornos de que estaba cargado” según criterios establecidos en 1793 por el sobrino de Ventura Rodríguez , Manuel Martín Rodríguez. Por desgracia este retablo fue destruido en la Guerra Civil (1936-1939), salvándose sólo el monumental lienzo de Rizi que todavía preside la cabecera, flanqueado en los laterales por un Santiago Matamoros, y otra Liberación de San Pedro atribuida a Ángelo Nardi que quizás fuese ejecutada para un retablo anterior. En 1965 la iglesia fue restaurada por Francisco Caballero Lasierra, y nuevamente entre 1996 y 2004 por José Miguel Ávila Jalvo; aunque la intervención más completa en el interior del templo se ha llevado a cabo entre 2012 y 2015.
