Площадь, на которой стоит храм, называлась Торговой: церковь строилась для торгового люда, а не для гвардии и не для двора. Сначала здесь была деревянная постройка 1745—1747 годов. Каменную возводили с 1761 по 1769 год на месте разобранной деревянной. Автора называют предположительно: Христиана Кнобеля, а также план Пьетро Трезини. Освятили храм 9 апреля 1783 года в честь иконы, одной из самых почитаемых в Московской Руси: от закладки до освящения прошло больше двадцати лет.
Стиль у здания переходный, от барокко к классицизму: барочная сложность ещё держится, но линии уже тянутся к ясности. Отдельно стоящая двухъярусная колокольня появилась в 1791 году по проекту Джакомо Кваренги и читается как самостоятельная постройка. В 1830—1831 годах Авраам Мельников пристроил притвор, в 1848-м Франц Руска добавил колокольне ещё ярус, а в 1850—1853 годах соорудил 2 часовни и ограду.
Внутри 2 храма: верхний холодный Владимирский и нижний тёплый во имя преподобного Иоанна Дамаскина. Иконостас верхнего перенесли сюда в 1808 году из домовой церкви Аничкова дворца — он выполнен по рисунку Растрелли. Паруса центрального купола украшают скульптурные евангелисты, а своды нижней церкви были расписаны; росписи утрачены в середине двадцатого века. После возврата церкви службы сначала шли только в верхнем храме, а иконостасы для нижнего делают постепенно, в стиле елизаветинского барокко, обыгрывая мотивы верхнего.
Приходская биография храма оказалась теснее связана с литературой, чем с архитектурой. В 1828 году здесь отпевали Арину Родионовну, няню Пушкина: родители поэта снимали квартиру рядом, в Свечном переулке, и близость эта объясняет выбор храма. С 1865 года при церкви действовало благотворительное общество с детским приютом и женской богадельней. Прихожанином Владимирской церкви в последние годы жизни был Фёдор Достоевский: его дом стоял в двух шагах от храма.
В 1932 году храм закрыли и отдали фабрике «Ленмашучёт», которая занимала здание больше полувека. Вернули его епархии в августе 1989 года, освятили 7 апреля 1990-го, статус собора он получил в 2000 году, а нижний храм после капитального ремонта открыли в сентябре 2018-го. Купола золотили ещё в 1886 году, но в 1930-х позолоту смыли и покрасили их чёрной краской. Новое золочение шло с 2014 по 2019 год, и теперь его видно с проспекта издалека. От церкви получили имена Владимирский проспект и Владимирская площадь.
