Константино-Еленинская церковь — самый первый в Акмолинске православный храм. Церковь возвели в 1854-1856-х годах по просьбе местного священника. Однопрестольная церковь была построена в центре казачьей крепости за счёт войсковой казны. Строительством церкви руководил инженер-поручик Г. А. Воротников. Первым настоятелем церкви стал священник Михаил Никольский.

В 1900 году по приказу акмолинского казачества храм перенесли на площадь старого Акмолинска, где и находится по сей день. По архитектурным характеристикам храм является по плану однопрестольным, пятиглавым, выдержан в форме правильного креста. Длина постройки 33 метра, ширина 8 метров. В настоящее время она оштукатурена и производит впечатление каменной.

В 1938 году церковь закрыли, убрали кресты и разрушили колокольню, превратив в краеведческий музей. В 1941-1942 годах в здании церкви размещался отдельный батальон связи 29-й стрелковой дивизии, формировавшейся в Акмолинске. В 1942 году православные горожане добились от местной власти, чтобы этому зданию вернули его изначальное предназначение. Собор находится по адресу: проспект Республики, 12.