En la década de 1860, los habitantes de Zhuravlevka decidieron construir un templo, lo que estaba relacionado con el rápido crecimiento de la ciudad y la inclusión de su territorio en su composición. La población de Zhuravlevka, así como de los pueblos y aldeas cercanas que más tarde se convirtieron en parte de la parroquia de Pedro y Pablo, estaba en aumento. Se estima que había alrededor de 3 mil feligreses, entre los cuales había campesinos estatales, comerciantes, mercaderes y nobles.

La asamblea parroquial decidió erigir un templo en honor a los apóstoles Pedro y Pablo, ya que en la ciudad no había un templo dedicado a estos santos, y los altares en otras iglesias requerían reparaciones o habían sido destruidos. Antes de esto, los habitantes de Zhuravlevka asistían a la iglesia de la Natividad de la Santísima Virgen María. Los iniciadores de la construcción fueron los feligreses, quienes encabezaron el comité de construcción. Entre ellos estaban los comerciantes de Járkov Iván Vasílievich Yákovlev con su esposa Pelaguía, Alexéi Ivánovich Levchenko, Iván Gavrilovich Vikhrev, Anna Ilinichna Checherina y el campesino Dmitri Petrovich Stronov. En 1870, Iván Vasílievich Bolotov legó 25 mil rublos para la construcción del templo, que debía ser construido primero después de su muerte. Bolotov, comerciante de primera guilda, se dedicaba al comercio y donaba a las iglesias, pero al final de su vida decidió apoyar un gran proyecto. En ese momento, entre las personas ricas era común dejar grandes sumas para la caridad, lo que se consideraba un rasgo nacional de los slobozhans.

Después de presentar una solicitud a la Consistoría, se aprobó el proyecto del templo, desarrollado por el arquitecto diocesano, y en 1872 comenzó la construcción. El comité de construcción, que incluía a los comerciantes Yákovlev y Levchenko, así como al campesino Stronov, adquirió un terreno de la general Kózlyanina para la construcción del templo. Más tarde se compró otro terreno para la casa del sacerdote y el diácono. El plano de la tierra y la escritura de compra fueron entregados a la Consistoría espiritual en 1882 por el primer rector de la iglesia de Pedro y Pablo, Nikolái Pantelimonov.

Para 1875, el templo fue construido en forma de barco con tres altares. En el lado sur se construyó una casa para la escuela parroquial. El 21 de septiembre de 1875, el arzobispo Savva consagró el altar norte, donde había un altar en honor al beato Basilio, el protector celestial de Basilio Bolotov. El altar principal en honor a los apóstoles Pedro y Pablo fue consagrado por el obispo Benjamín el 5 de septiembre de 1876. El último altar en honor a Juan Bautista y la mártir Pelaguía, protectores de los comerciantes Yákovlev, fue consagrado por el arzobispo Ambrosio el 12 de octubre de 1886. El templo se mantenía con donaciones, de las cuales se recaudaron 4850 rublos. Las frescos dentro del templo fueron pintados por el artista moscovita Iván Chelyapov.

En 1902, en el territorio del templo se estableció una escuela parroquial, que más tarde pasó a la ciudad. En 1907 se discutió la construcción de una escuela parroquial. La educación gratuita fue un paso importante hacia la educación universal. En 1896, solo había una escuela dominical en Zhuravlevka y sus alrededores, donde se enseñaban lectura, Ley de Dios, aritmética y otras materias.

En diciembre de 1909, se llevó a cabo la primera reunión del "Círculo de los celosos de la Iglesia Ortodoxa", que despertó el interés de 250 personas. En 1910, la cólera pasó de largo por la parroquia. En 1917, con el inicio de la revolución, los bolcheviques cambiaron el orden de vida habitual, emitiendo decretos sobre la separación de la iglesia y el estado, la prohibición de las procesiones y la enseñanza de la Ley de Dios. Los feligreses intentaron llevar a cabo una procesión, pero las autoridades la prohibieron.

Con la llegada de las tropas germano-gaydamak, los bolcheviques continuaron la agitación, pero sus llamados no encontraron respuesta. En agosto de 1919, los feligreses participaron en un servicio de acción de gracias por la liberación de la ciudad de los bolcheviques. El protoiereo Nikolái Smirnov escribió que con el nuevo poder, la vida comenzó a mejorar.

La iglesia de Pedro y Pablo funcionó hasta 1937, cuando su rector Andrei Tolmachev fue arrestado y fusilado en 1938. En 1945, la iglesia fue registrada por las autoridades, y se reanudaron los servicios. Durante la guerra, la iglesia sufrió daños por un incendio provocado por los bolcheviques en retirada, y fue utilizada por los alemanes como establo.

Las cúpulas de la iglesia fueron reemplazadas por otras nuevas y más grandes, y se convirtió en una iglesia de cinco cúpulas. Se realizaron trabajos de restauración en el interior, se instaló electricidad, se llevó agua y el suelo se convirtió en de madera. El territorio de la iglesia fue embellecido.

En 2003, comenzaron los trabajos de restauración. La iglesia fue enlucida y blanqueada, se colocó un nuevo suelo y se inició la pintura. Entre 2004 y 2006 se completó la pintura en estilo académico. En 2004 se realizaron trabajos en el altar, se instalaron un nuevo iconostasio y una reja de forja. Por la noche, la iglesia se ilumina artísticamente, convirtiéndola en uno de los lugares de interés de Járkov.