6 июня 1905 года на станции Шилка прошло собрание, где обсуждали необходимость строительства церкви, выбор места и финансирование. На этом собрании учредили наблюдательный комитет для контроля пожертвований и проверки отчетности по строительству храма. Также был установлен порядок созыва собраний членов комитета жертвователей. В то время в селе Митрофаново уже существовал храм в честь святителя Николая, который посещали жители Шилки. Однако с развитием станции и ростом населения возникла потребность в собственном храме, так как большинство жителей Шилки были железнодорожниками с посменной работой, что затрудняло посещение храма в Митрофаново.

29 июня священник Митрофановской Никольской церкви Иаков Знаменский, вместе со священником Городищенской церкви Михаилом Пляскиным и диаконом Николаем Знаменским, при участии около 1000 молящихся, провел закладку храма на станции Шилка во имя святых Апостолов Петра и Павла. Иаков Знаменский предложил присутствующим возложить по камню в основание храма.

К 1908 году на средства железнодорожных прихожан церковь была построена и 30 марта 1908 года освящена епископом Забайкальским и Нерчинским Мефодием. Здание церкви было деревянным с колокольней, покрыто кровельным железом, с позолоченными тремя главами. В начале 1909 года при Шилкинской железнодорожной церкви был образован самостоятельный приход. 7 апреля 1909 года настоятелем Петро-Павловской церкви назначили священника Николая Павловича Виноградова. До июня 1909 года храм относился ко второму благочинному округу железнодорожных церквей, а 24 июня 1909 года был передан в 25-е благочиние Забайкальской и Неринской епархии. Нижний придел храма был выложен из тёсанного камня и засыпан землёй, создавая впечатление, что верхний предел стоит на холме. Верхний придел был сложен из бруса в деревне Кибасово и через три года перенесен на теперешнее место. Благодаря усилиям железнодорожников и жителей района появился этот храм в честь святых апостолов Петра и Павла. Штат дореволюционного храма включал 5 священнослужителей: протоиерея, двух иереев, диакона и псаломщика.

В 1929 году храм закрыли и вскоре использовали как пересылочную тюрьму, куда попадали в первую очередь священники и так называемые кулаки. После тюрьмы в здании размещались кузница, ремесленное училище, овощехранилище и зерновой склад, затем спортзал и музей. Лишь в 1990 году среди местных депутатов нашелся человек, который помог собрать и оформить общину верующих. После этого начались длительные хлопоты по выселению бывших жильцов. Спортзал убрали, но музей оставался в подвале, и дела у прихожан продвигались медленно.

Здание досталось верующим в плачевном состоянии: потолок был как решето, окна заколочены досками, стены прогнуты, отопительная система отсутствовала, не было куполов, крестов, икон и церковной утвари. В 2002 году объявили сбор средств на колокола, и за полтора года собрали сумму, достаточную для покупки шести колоколов, самый большой из которых весит 7 пудов.

В настоящее время при храме работает воскресная школа и трапезная, где получают питание не только послушники храма, но и многие малоимущие. Для паломников действует благотворительная гостиница на пять мест.