Au moment où Tessin soumit ses projets, le tsar était mort et le projet coûteux fut suspendu. Deux ans plus tard, Giuseppe Trezzini, architecte de la ville de Saint-Pétersbourg, fit défricher le terrain derrière les bâtiments des Douze Collèges et construisit une modeste église en bois, qui fut consacrée par Théophane Prokopovitch à saint André le . C'était une structure austère rationnelle avec peu de prétentions stylistiques. L'impératrice Anne a fait don de meubles à l'église, tandis que les icônes requises par l'usage orthodoxe ont été prises dans une chapelle du palais Menchikov voisin.
L'église en bois étant jugée trop petite pour abriter sa congrégation croissante, Trezzini conçut une église en pierre, qui fut fondée le à proximité de la cathédrale en bois. La nef de l'église a été érigée en cinq ans, mais des travaux de décoration ont empêché sa consécration jusqu'en 1760. C'est ici que Mikhaïl Lomonossov et Vassili Trediakovski ont prêté serment en tant que professeurs de l'Académie impériale des sciences le . La structure, dédiée au nom des Trois Saints Hommes, existe toujours.
Vue de la cathédrale au tournant du XIXesiècle.
Le , la cathédrale en bois fut frappée par la foudre et incendiée. L'architecte Alexander Whist (1722-1794) fut chargé de concevoir une nouvelle cathédrale de pierre. Bien que fondée le , l'église a pris 22 ans pour être achevée. Un retard est dû à l'effondrement de sa coupole le , catastrophe qui conduit à l'arrestation de l'architecte. Ce n'est que le que la cathédrale rose pastel à cinq dômes fut consacrée.
La décoration de la cathédrale est sobre (photo), bien que l'empereur Paul, en réaffirmant son importance en tant qu'église capitulaire du plus ancien ordre de chevalerie russe, ait fait décorer l'entrée d'un relief représentant l'ordre porté par deux anges. Une place spéciale fut réservée dans la cathédrale au tsar jusqu'en 1813.
Le clocher pyramidal, attaché à l'église par un réfectoire, a été construit en deux niveaux en 1784-1786 et abritait autrefois dix cloches dont la plus grande pesait plus de quatre tonnes. Le sommet du beffroi a été rénové en 1850. Sept ans plus tard, l'intérieur de la cathédrale a été rénové. Lorsque le premier pont permanent sur la Neva a été construit dans les années 1850, une chapelle sur le pont est devenue affiliée à la cathédrale.
Intérieur de la cathédrale Saint-André
Après la révolution russe de 1917, les bolcheviks ont confisqué de nombreux objets de valeur de l'église. Le , une foule de plusieurs centaines de fidèles tenta de défendre les icônes et se heurta aux membres du «comité d'expropriation». En raison des désordres, la cathédrale fut cédée aux rénovateurs, une secte soutenue par l'État qui cherchait à concilier les idéaux du christianisme et du communisme.
Le , la cathédrale fut fermée, ses prêtres arrêtés et les cloches détruites. Cependant, l'impressionnante iconostase baroque a été restaurée, tandis qu'une icône du XVIIesiècle avec les portraits du patriarche Nikon et du tsar Alexis a été transportée au musée Russe. Pendant le siège de Leningrad, le dôme était équipé de canons qui ont aidé à protéger la zone des bombardements intensifs.
En 1992, la cathédrale Saint-André et l'église des Trois Saints Hommes ont été rendues à l'Église orthodoxe russe. En 2001, un obélisque a été dévoilé devant l'église pour célébrer le tricentenaire de l'ordre restauré de Saint-André.
