After reaching third place in 1995 and 2007 their first championship was won in 2011. Before this they were one of the leading Kazakh teams in the football of the Soviet Union.
On 19 September 2008, Shakhter and Vostok were disqualified from the Kazakhstan Premier League for playing a fixed match, club coaches and management involved were banned from football for 60 months. On 2 October 2008, the FFK revisited their decisions. Shakhter were deducted nine points, Vostok were immediately expelled from the competition. The result of the game in question has been cancelled and all remaining Vostok games will be counted as won by 3–0 for their opponents.
Shakhter sacrifice a sheep the day before matches, as a tradition. This has led the People for the Ethical Treatment of Animals (PETA) to petition UEFA President Michel Platini for a ban on animal slaughter in European football. Laws regarding animal slaughter have made the custom impossible when playing away in some countries.