Закладка каменного храма состоялась в 1764 году. Строительство велось по проекту и под наблюдением архитектора А. Ф. Виста. Спустя два года после начала строительства своды храма обрушились. Архитектор был посажен под арест, но впоследствии оправдан. Обрушение храма вызвало задержку в его строительстве — освящение собора состоялось только в 1781 году.
В XIX веке Андреевский собор был расширен: к трапезной пристроены боковые приделы, произведены изменения в интерьере. Собор был закрыт в советское время, но его внешнее и внутреннее убранство практически не пострадало.
В плане храм представляет триконх с пристроенной с запада прямоугольной трапезной и колокольней. Пятиглавие храма решено в «растреллиевском» духе: массивный купол на восьмигранном барабане в центре и четыре стройных двухъярусных башенки по углам здания. Два нижних яруса колокольни в упрощенном виде воспроизводят композицию колокольни Никольского Морского собора. Большую ценность представляет сохранившийся в интерьере храма иконостас XVIII-XIX веков.