Основан е през 2009 г. от обединилите се „Мегаспорт“ и ФК „Алма-Ата“ под името „Локомотив“, Астана.
Първият треньор в историята на клуба е Вадиг Масудов. Той обаче не се задържа много и е сменен от Сергей Юран. Спонсор стават Казахстанските железници, а в Астана е построен стадион с капацитет 33 000 зрители. Юран подсилва отбора с бившите си съотборници от Спартак МоскваЕгор Титов и Андрей Тихонов. Освен тях, към отбора се присъединяват Патрик Овие и Андрей Карпович. Локомотив заема 2-ро място през сезон 2009. В началото на 2010 г. Титов и Тихонов напускат поради неплатени заплати. Треньор става немецът Холгер Фах. През 2010 г. „Локомотив“ завършва на 4-та позиция.
От 2011 г. се казва ФК „Астана“. През 2014 г. под ръководството на Станимир Стоилов печели първа титла на Казахстан в историята си. Също под негово ръководство, отборът за първи път влиза в групите на Шампионска лига, като заедно с това става първият казахстански отбор, който ще играе в групите. През 2017 г. печели четвърта поредна титла, а в групите на Лига Европа завършва на второ място, като продължава напред в директните елиминации.