Architektura Sobór reprezentuje urzędowy styl rosyjsko-bizantyjski. Jest to budowla pięciokopułowa, murowana. Główna kopuła rozmieszczona jest na dwunastobocznym bębnie, boczne – na ośmiobocznych. Kopuły nie zostały pokryte złotem na wyraźne polecenie cara Mikołaja I. Dwie z bocznych kopuł pełnią równocześnie funkcje dzwonnic. Największy dzwon w soborze waży 296 pudów. W świątyni funkcjonują trzy ołtarze: główny św. Pawła, prawy Świętych Konstantyna i Heleny oraz lewy św. Marii Magdaleny.
W świątyni znajduje się dziewiętnastowieczny ikonostas. Początkowo miał on zostać wykonany z pozłacanego drewna lipowego, jednak w 1850 architekt Kuźmin poprosił cara o zgodę na wykonanie go z drewna cyprysowego, które lepiej harmonizowałoby z kolorystyką ikon. Mikołaj I zgodził się i sam sfinansował wykonanie ikonostasu. Konstrukcję zaprojektował F. Sołncew, zaś wykonał ją Skworcow, natomiast ikony napisali Bruni, Scotti, Zawjałow, Sieriebriakow i Piernic.