В 1997 году Астана стала столицей Республики Казахстан, в связи с чем возникла необходимость строительства в городе кафедрального храма Русской Православной Церкви. В 2004 году, с назначением на Астанайскую и Алма-Атинскую кафедру митрополита Мефодия (ныне на кафедре Пермской и Соликамской епархии), начались проектно-изыскательские работы.
В январе 2006 года состоялись закладка камня и освящение фундаментной плиты строящегося собора. К апрелю были смонтированы перекрытия, а на Пасху в строящемся соборе было совершено первое богослужение. После этого богослужения и совершение треб в строящемся храме стали регулярными.
В 2007 году для собора была создана звонница.
К Пасхе 2009 года было закончено возведение стен и сводов собора, началась облицовка наружных стен белым мрамором.
В августе 2009 года митрополит Астанайский и Алма-Атинский Мефодий в присутствии акима г. Астаны И.Н. Тасмагамбетова и посла Российской Федерации в Республике Казахстан В.Н. Бочарникова совершил освящение пяти куполов и крестов собора.
17 января 2010 года, в неделю пред Богоявлением и в праздник Собора 70-ти апостолов, Святейший Патриарх Московский и всея Руси Кирилл совершил чин великого освящения главного престола в честь Успения Пресвятой Богородицы в верхнем храме собора Успенского кафедрального собора, после чего возглавил Божественную литургию в новоосвященном храме.
Боковые приделы верхнего храма посвящены святым равноапостольным Кириллу и Мефодию, учителям Словенским, и Архистратигу Михаилу и прочим Небесным Силам бесплотным. Престол нижнего храма посвящен Собору новомучеников и исповедников Казахстанских.
Общая площадь собора составляет более 2000 кв. м., вместимость — до 4000 человек, высота храма — 68 м.
Первым настоятелем и куратором строительства собора (до марта 2010 года) являлся благочинный приходов Астанайского округа архимандрит Серапион (Дунай).
Настоятель — архимандрит Сергий (Карамышев).
4 июня 2011 года на заседании Синода Митрополичьего округа Русской Православной Церкви в Республике Казахстан под председательством митрополита Астанайского и Казахстанского Александра было принято решение о возведении в Астане при Успенском кафедральном соборе здания Синода Православной Церкви Казахстана и духовно-культурного центра имени святых равноапостольных Кирилла и Мефодия (журнал № 21).
Проект получил благословение Святейшего Патриарха Московского и всея Руси Кирилла и был одобрен Президентом Республики Казахстан Н.А. Назарбаевым.
19 сентября 2011 года, в день принесения в Астану главной святыни Русской Православной Церкви Заграницей — Курской-Коренной иконы Божией Матери «Знамение», по окончании Божественной литургии митрополит Александр и гости-архипастыри освятили близ Успенского собора строительную площадку и закладной камень в основание административного и духовно-культурного центра Казахстанского митрополичьего округа с храмом в честь Астанайской иконы Божией Матери.
