Впервые упоминание о Покровском храме встречается в «Дозорной книге» Григория Киреевского, датированной 1615 годом: «Слобода Беломестных атаманов и казаков, а в слободе церковь во имя Покрова Пресвятой Богородицы, древяна, клецки, с папертью, а в церкви образы и колокола и всякое церковное строение приходских людей». Определение «новая» применительно к ней не употреблено, так что ее появление можно датировать началом XVII века.

Известно, что в 1700 году святитель Митрофан, первый епископ Воронежский, дал благословенную грамоту на построение нового храма, так как прежняя деревянная церковь пришла в ветхость. В 1736 году началось возведение каменной церкви.

В 1748 году был освящен придел во имя Сретения Господня. В конце XVIII века в храме появился второй придел, во имя иконы Божией Матери, именуемой «Знамение»; он был освящен 11 февраля 1796 года епископом Воронежским и Черкасским Мефодием (Смирновым, †1799). В 1791 году была построена невысокая трехъярусная колокольня. На звоннице самый крупный из колоколов, доставленный из Москвы, весил 181 пуд 5 фунтов (немногим меньше трех тонн).

Вскоре назрела необходимость в перестройке главного храма. Основные работы по его возведению были завершены в 1835 году, но отделка затянулась до 1841 года, и церковь была освящена 14 июля 1841 года святителем Антонием, архиепископом Воронежским и Задонским. Храмовая часть с ионическим портиком и широким барабаном главного нефа придает Покровскому храму величественный вид.

В 1847 и 1848 годах освящены теплые приделы — во имя Сретения Господня и во имя иконы Пресвятой Богородицы, именуемой «Знамение», — устроенные в трапезной купцом С.П. Евфимовым и «тщанием прихожан».

При очередном ремонте в 1872 году усилиями церковного старосты В.О. Ухина были возобновлены в трапезной оба придела, а иконостасы главного храма и приделов покрыты червонным золотом.

В архитектурном отношении интересен дом священников, построенный рядом с храмом по «образцовому» (типовому) проекту в начале XIX столетия. В храмовой ограде располагалось небольшое кладбище, где были погребены священники и многолетние церковные старосты.

В 1904 году в Покровском храме насчитывалось 1282 прихожан. Штат церкви состоял из двух священников, одного диакона, двух псаломщиков.

Богослужения в храме совершались до 1932 года. После закрытия здесь был организован Дом обороны, а затем в церкви расположился выделившийся из краеведческого антирелигиозный музей. Под куполом закрепили маятник Фуко.

В августе 1945 года группа верующих во главе с М.П. Вдовиным и Ф.Т. Хреновым начали ходатайствовать о возвращении храма верующим. Дважды эти ходатайства поддерживал своими обращениями Святейший Патриарх Алексий I (Симанский, †1970). 2 марта 1948 года Совет по делам Русской Православной Церкви принял решение: «Удовлетворить ходатайство верующих об открытии Покровской церкви в городе Воронеже и предложить уполномоченному Совета при Воронежском облисполкоме зарегистрировать общину и оформить передачу ей здания церкви и культового имущества». В мае 1948 года здание передали православной общине.

В 1948 году при епископе (впоследствии митрополите) Воронежском и Липецком Иосифе (Орехове) из Никольского храма в Покровский была перенесена архиерейская кафедра. С тех пор Покровский храм является кафедральным собором города Воронежа

14-15 ноября 1998 года состоялся первый в истории визит в Воронежскую епархию Предстоятеля Русской Православной Церкви. Святейший Патриарх Московский и всея Руси Алексий II совершил молебен у мощей святителя Митрофана, всенощное бдение и Божественную литургию в Покровском кафедральном соборе.