The club formed as the result of a merger between FC Alma-Ata and Megasport in the beginning of 2009 as FC Lokomotiv Astana. Later they moved to newly built Astana Arena. The club has benefited from a high salary role which has enabled them to attract players of status to the club. Tikhonov and Titov first of all came from the Russian Premier League. Several more followed such as Patrick Ovie, Baffour Gyan and Maxim Shatskikh, which was again a very high profile capture for the club. The majority of their other players have arrived from other clubs of the Kazakhstan League, mostly on free transfers from the clubs which were absorbed to make the club and several which last year went into bankruptcy.
Although Lokomotiv won the Kazakhstan Cup in 2010, they were ineligible for a UEFA license since they had not yet existed for at least three years. So they were not able to start in 2011–12 UEFA Europa League.
On May 20, 2011, FC Lokomotiv Astana renamed to FC Astana.