Az FC Tobolt 1967-ben alapították, bár a csapatnak otthont adó Kostanayban a futball már a cári időkben megjelent, 1910-ben írtak először a helyi újságok a játékról, amely igazán csak a harmincas években terjedt el a vidéken. A II. világháború után a Kazah SZSZK-ban regionális bajnokságok alakultak, melyben Kostanay városa is részt vett. A mai ismert FC Tobol Kostanay 1967-ben jött létre Torpedo néven, de még az abban az évben átnevezték Motoristra. A csapat becsatlakozott a szovjet ligarendszerbe, sokáig az alsóbb ligákban szerepelt, 1981-ben jutott fel a Szovjetunió másodosztályába. A csapat első nemzetközi mérkőzését 1984-ben Laosz válogatottja ellen játszotta, és 5-1-re győzött. A kazah futball-ligának alapítása óta tagja, első szezonjában a 13. helyen zárt a 24 induló közül. Mai nevét 1995-ben nyerte el. A kilencvenes években a megszűnés szélére került a klub, mivel szinte az összes játékosa elhagyta a csapatot, ám a pénzügyi segítségeknek köszönhetően a csapat újra össze tudott állni. 

A csapat élére 2003-ban került először külföldi edző az orosz Vladimir Mukhanov személyében. A szakember vezetésével a klub bejutott a Kazah-kupa döntőjébe, ahol vereséget szenvedett a Kalyraty Almaty csapatától. A klub 2005-ben mindössze egy ponttal maradt le a bajnoki címről, így indulhatott az UEFA Kupa selejtezőjében. 2007-ben ismét másodikak lettek, azonban megnyerték a Kazah Kupát, így indulhattak az Intertotó-kupában, amelyben meglepetésre a győztesek között végeztek (az Intertotó-kupában indulók nem a kupát nyerték meg, hanem jogot szereztek, hogy részt vegyenek az UEFA-Kupa selejtezőben, 2007-ben nyolc csapat lett „nyertes”). A Tobol az UEFA-Kupa selejtező első körében kiesett. 2008-ban az Aktobe és a Tobol is 67 ponttal fejezte be a bajnokságot, így a szabályok szerint „aranymeccsre” került sor, mely 1-1-es döntetlennel zárult, így a gólnélküli hosszabbítás után büntetőpárbajra került sor, melyet 5-3-ra elvesztett a kustanayi gárda. Két évvel később, 2010-ben végre összejött a hőn áhított bajnoki cím az FC Tobol csapatának. Ekkor lépett először és mindmáig utolsó alkalommal pályára a klub a Bajnokok Ligája selejtezőjében, azonban a Slovan Bratislava nehéz falatnak bizonyult, és a kazah csapat 3-1-es összesítéssel búcsúzott a nemzetközi színtérről. Az elmúlt évtizedben gyengébben alakult a csapat szereplése, egyszer odafértek a dobogóra, legtöbbször a középmezőnyben végeztek, de legalább a kiesés réme sose fenyegette őket. A Tobol 2020-ban a második helyen végzett, így indulhatott a Konferencia Liga selejtezőben, ahol 2021 nyarán nagy meglepetésre kiejtette a Hajduk Splitet.  A tavalyi szezonban története során másodszor Kazahsztán bajnoka lett, így idén ismét részt vehet a Bajnokok Ligája selejtezőinek küzdelmeiben.

Kazahsztánban a szezon 2021 októberében zárult, a bajnokságot 61 ponttal nyerte a Tobol, négy pontot verve a második Astanára. A csapat mindössze egyszer szenvedett vereséget a szezonban, legjobb góllövőjük a szerb Nemanja Nikolic lett 17 találattal. Az FC Tobol februárban megnyerte a Kazah Szuperkupát is, 2-1-re legyőzve a Kalyraty Almaty csapatát. A márciusban indult kazah Premier League-ben eddig 12 meccs ment le, a Tobol Kostanay jelenleg az ötödik helyen áll. Legutóbbi meccsükön, május végén 4-2-re nyertek az utolsó helyen álló Makhtaraal ellen. 

A csapat összértéke a mértékadó Transfermarkt szerint 11.13 millió euró, legértékesebb játékosuk az 1.7 millióra taksált üzbég-orosz Igor Serveer, rajta kívül még egy játékos éri el az egymilliós értéket, az észak-macedón Aleksa Amanovic. Keretükben szinte kizárólag kazah, illetve kelet-európai játékosok találhatóak, a portugál Rúben Brígidót leszámítva. A csapat vezetőedzője májusig a 45 éves kazah szakember Aleksandr Moskalenko volt, jelenleg Milan Milanović látja el ezt a tisztséget. 

Az FC Tobol otthona az 1964-ben átadott Zentralstadion Kostanay, amely 8050 ember befogadására alkalmas.