Sowjetische Meisterschaft

Der Verein wurde im Jahr 1963 gegründet. In der sowjetischen Meisterschaft spielte der Club meist in den untersten Ligen.

Kasachische Meisterschaft

Seit der Unabhängigkeit Kasachstans 1991 spielte der Verein unterbrochen in der höchsten Spielklasse des Landes. Die beste Platzierung wurde in den Jahren 1997 und 1998 mit jeweils dem fünften Rang erzielt. 1994 konnte der erste große Erfolg auf der nationalen Ebene gefeiert werden, als im Finale des kasachischen Pokals der FK Aqtöbe mit 1:0 bezwungen wurde. Wostok Östemen war 2008 aufgrund eines verschobenen Spiels gegen Schachtjor Qaraghandy ans Tabellenende strafversetzt worden, durfte aber dennoch 2009 in der höchsten Liga mitspielen. Nach der Saison 2009 musste das Team aufgrund finanzieller Schwierigkeiten in die zweite kasachische Spielklasse absteigen und schaffte in der darauffolgenden Spielzeit den sofortigen Wiederaufstieg. Nach der enttäuschenden Saison 2011 folgte der erneute Absturz in die Zweitklassigkeit, allerdings wurde in der darauffolgenden Spielzeit der sofortige Wiederaufstieg geschafft.

Wegen finanzieller Schwierigkeiten und dem Ausbleiben sportlicher Erfolge wurde am Ende der Saison 2015 die Fusion von Wostok Öskemen und Spartak Semei zum neuen Verein FK Altai Semei verkündet.

• Logo bis 2011