В письменных источниках церковь упоминается сначала как церковь Николая Чудотворца за Петровскими воротами (1625 год), затем как церковь Климента, папы Римского что на Яру; церковь Климента, папы Римского в Стрелецкой слободе в Михайлове приказе Рчинова; церковь Знамения Пресвятой Богородицы и Климента папы Римского на Трубе, в Стрелецкой слободе.

Полковой каменный храм в честь Знамения Пресвятой Богородицы был построен стрельцами вместо ранее существовавшего деревянного храма во имя святого священномученика Климента, папы Римского. Храм находился на берегу речки Неглинной неподалеку от Трубной площади, на границе стрелецкой слободы Земляного города. 

1 июня (по старому стилю) 1679 года при государе Феодоре Алексеевиче и патриархе Иоакиме стрельцами полковника Никифора Ивановича Колобова на месте ранее существовавшего и сгоревшего в 1676 году деревянного храма во имя святого священномученика Климента, папы Римского был заложен первый камень в основание будущей церкви во имя чудотворной иконы Божией Матери «Знамение». Этот образ Пресвятой Богородицы исстари почитался у православного воинства за его особое покровительство в ратном деле, за его «пленение ратников и покорение супостатов». Изображение Божией Матери «Знамение» было принято на очень многих военных знаменах и иконах, которые несли в сражениях впереди войск. 

Стрелецкая слобода за Петровскими воротами Белого города к этому времени насчитывала более 1000 дворов. Церковь, посвященная образу Божией Матери «Знамение», в 1681 году украсила собой не только деревянную стрелецкую слободу, но и древнюю столицу. В ней воплотилась вся красота величественных форм русского узорочья: уникальное даже для Москвы многоглавие в одиннадцать куполов, узорная шатровая колокольня, кованые кресты, кокошники, наличники, резные порталы.


Строительство каменной церкви обошлось в 1300 рублей, по тем временам сумму огромную. Поиздержавшись, стрельцы обратились за помощью к государю. Вот подлинные строки «челобитной» грамоты: «Царю государю и великому князю Федору Алексеевичу всея Великия и Малая и Белая России самодержцу бьют челом холопы твои стольника и полковника Никифора Ивановича Колобова пятидесятники и десятники и рядовые всего приказу стрельцы. Твоим великого государя жалованием, а нашим холопей твоих обещанием построена у нас церковь каменная во имя Знамения Пресвятой Богородицы да в приделе священномученика Климента папы Римского, а Божия милосердия образов построить нам холопем твоим нечем (...)».

Через пятнадцать дней после подачи прошения по приказу царя Фёдора Алексеевича из казны Оружейной палаты в Знаменскую церковь были переданы 41 святая икона праотцев, пророков и апостолов, а также южная дверь иконостаса. Позднее главный купол храма был увенчан крестом с короной, что свидетельствовало о присутствии царственных особ за Божественной литургией в храме и их особого благорасположения к этой святыне.

В честь храма переулки, окружавшие его, стали называться Знаменскими.

Полковой храм стал духовной осью, объединяющей место - стрелецкую слободу и стрельцов - «государевых людей».

В 1754 году с юго-восточной стороны храма был устроен ещё один придел во имя Всех Святых. Во время страшного пожара 1812 года храм пострадал меньше, чем другие московские святыни: сгорела только крыша, были повреждены двери и окна. По желанию прихожан в 1819 году Климентовский придел храма был переосвящён во имя преподобного Сергия Радонежского - игумена Земли Русской.

После подавления стрелецкого восстания и уничтожения самого сословия по указу Петра I стрелецкие полки были расформированы. Но храм Знамения Пресвятой Богородицы продолжал жить и служить «людям государевым». На месте стрелецкой слободы позднее размещались Петровские казармы, а еще позже обосновалась Московская жандармерия. Здесь же после революции обосновалось и Центральное Управление Московской милиции.

В годы гонений Знаменский храм чудом сохранился и не был взорван, как, например, близстоящий храм Преображения Спаса на Песках в Большом Каретном переулке. Храмовые земельные владения, на которых находились богадельня, дом притча и несколько доходных домов, были национализированы. Богоборческая власть изъяла всё церковное имущество: редкие богослужебные книги XVII - XVIII веков, старинную церковную утварь, богослужебные сосуды, бесценные иконы с частицами мощей и другие святыни. 16 января 1932 года постановлением Президиума Мособлисполкома храм Знамения Пресвятой Богородицы был закрыт «в связи с острой необходимостью в помещении» под архив Управления Московской милиции.

В 1950-х годах здание храма было передано Институту химической физики Академии наук СССР. Здесь, в закрытых цехах и лабораториях, трудились десятки научных сотрудников, изготовляя и испытывая силикатный кирпич, кирпич будущего. Вся эта деятельность привела к тому, что церковная колокольня наклонилась и оказалась в аварийном состоянии, на фасадах появились множественные трещины. Разделенный железобетонными перекрытиями на три этажа и под самый купол заполненный сплетениями проводов, силовых кабелей, трансформаторами, испытательными стендами, аппаратурой химического анализа, храм полностью утратил внутренний интерьер. Многотонные токарные и фрезерные станки, прессы заняли придел преподобного Сергия Радонежского, муфельные печи - придел Всех Святых. В Знаменском приделе располагались испытательные лаборатории, здесь же хранились огромные емкости с химическими реактивами и растворами. Алтари были отведены под кабинеты руководства и туалет.

В 1968 году начался ремонт храма и колокольни, реставрация 1970—1980-х годов проводилась с восстановлением таких элементов первоначального облика, как главы и наличники на окнах. В киоте над входом в колокольню, вокруг некогда бывшей здесь иконы, сохранилась фреска с изображением ангелов.

В 1991 году была предпринята попытка передать Знаменскую церковь Русской Православной Церкви. Процесс затянулся на три долгих года. 4 декабря 1994 года, в день Введения во храм Пресвятой Богородицы, клирику храма Вознесения Господня у Никитских ворот («Большое Вознесение») священнику Александру Трепыхалину был вручен Указ Святейшего Патриарха Московского и всея Руси Алексия на настоятельство «вновь открываемого храма Знамения иконы Божией Матери за Петровскими воротами г. Москвы с поручением ему попечения о скорейшем возвращении Церкви ранее принадлежавшего ей храма и возобновления в нем богослужений».

10 декабря 1997 года в день Знамения Пресвятой Богородицы в храме возобновились регулярные богослужения, состоялась первая после закрытия храма Божественная литургия. К освящению придела Всех святых была отреставрирована икона Божией Матери «Знамение», подарена огромная икона Всех Святых и написана икона святых благоверных князей Петра и Февронии, Муромских чудотворцев. Позднее появились и другие святыни.

В Великую Субботу 2001 года храм посетил Святейший Патриарх Алексий II.

Знаменский храм за Петровскими воротами оказался единственным храмом в Москве, сохранившим свое историческое предназначение: служить «государевым людям» - современным потомкам московских стрельцов, воинам правопорядка. Заботой о стрелецком храме и верностью традиционным ценностям было продиктовано обращение начальника московской милиции Владимира Васильевича Пронина к Святейшему Патриарху Московскому и всея Руси Алексию II о придании Знаменскому храму статуса гарнизонного.

Резолюция от 21 ноября (день Архистратига Божия Михаила - покровителя воинства) 2002 г. Его Святейшества гласит: «Радует желание ГУВД возродить веками существовавшую взаимосвязь Армии и Церкви, а через то и историческую преемственность между храмом и воинскими гарнизонами, размещавшимися на месте бывшей стрелецкой слободы. Благословение и помощь Божия да сопутствуют всем труждающимся на данном поприще. Храму Знамения иконы Божией Матери за Петровскими воротами Нами усваивается статус храма при Главном управлении внутренних дел по городу Москве».

Большую помощь по восстановлению гарнизонного храма оказал начальник ГУ МВД России по г. Москве Владимир Александрович Колокольцев. При его участии на спонсорские средства в полном объеме начались ремонтно-реставрационные работы, которые продолжаются по сей день.

В 2007 г. основные работы по реставрации шли в приделе преподобного Сергия Радонежского, был изготовлен иконостас для Сергиева придела, который установили в декабре 2008 г.

В феврале 2008 г. Филатовскими реставрационными мастерскими (г. Москва) началось восстановление уникальной живописи в Сергиевом приделе, проводившееся по сохранившейся фотофиксации. В марте 2009 г. работы по восстановлению живописи завершились, а в октябре 2010 г. были подняты хоросы и повешены светильники, изготовленные по специальной технологии для этого придела.

В 2011 году отреставрированы колокольня и крыши над алтарем Знаменского придела и над приделом Всех Святых. В начале мая 2012 г. были привезены большие колокола (от 3 т 400 кг), а в середине октября 2012 г. доставлены все остальные, всего 14 колоколов.

В Великую Субботу 2012 г. случилось еще одно знаменательное для нашей общины событие - посещение Святейшего Патриарха Московского и всея Руси Кирилла. На встрече со Святейшим Патриархом присутствовали: заместитель начальника ГУ МВД России по г. Москве — начальник полиции, генерал-майор полиции Голованов В.В., начальник Управления охраны общественного порядка, генерал-майор полиции Козлов В.А., начальник управления уголовного розыска, полковник полиции Баранов О.А., начальник Правового управления, полковник полиции Пантелеева Л.В. и другие сотрудники ГУ МВД.

В 2015 году на территории храма открыли памятник московским сыщикам, погибшим при исполнении служебного долга. Автор скульптуры — Иван Черапкин, заслуженный художник России.

В 2023 г. храму присвоен статус Подворья Патриарха Московского и всея Руси. 10 декабря 2023 г., в праздник иконы Божией Матери, именуемой «Знамение», Святейший Патриарх Московский и всея Руси Кирилл совершил чин великого освящения храма Знамения иконы Божией Матери за Петровскими Воротами при ГУ МВД России по г. Москве.

На протяжении трех столетий храм почти не изменил свой внешний облик. Даже во времена государыни Екатерины, увлекавшейся западными эталонами красоты, русская архитектура Знаменской церкви осталась нетронутой. Прежним осталось и предназначение храма - служить людям воинским, «государевым». Здесь, на этом месте, и сейчас находится знаменитая Петровка, 38 - Главное управление Министерства внутренних дел России по городу Москве (ГУ МВД России по г. Москве). И сегодня местность эта, пересеченная Колобовскими переулками, названными в честь стрелецкого полковника Никифора Колобова, богата учреждениями правоохранительных органов. Как и три века назад, здесь служит много «государевых» людей.