Első szezonjukban hatodikak lettek a [[Skót labdarúgó-bajnokság (negyedosztály)|negyedosztályban]], majd két évvel később megnyerték a ligát, és feljutottak a [[Skót labdarúgó-bajnokság (harmadosztály)|harmadosztályba]]. Itt két szezont töltöttek el, majd a második helyen végeztek, és feljutottak a [[Skót labdarúgó-bajnokság (másodosztály)|másodosztályba]].
A [[2003–2004 a skót labdarúgásban|2003–2004]]-es szezon a klubtörténelem legsikeresebbjei közé tartozik. Először [[2003]] [[november]]ébennovemberében 2–0-ra legyőzték ([[Steve Hislop]] és [[David Bingham]] góljaival) az [[Airdrie United FC|Airdrie Unitedot]], és elhódították a [[Scottish Challenge Cup]]-ot. Majd bejutottak a [[Skót labdarúgókupa|Skót Kupa]] elődöntőjébe, és csak az 1–1-et követő megismételt meccsen kaptak ki 3–2-re a [[Dunfermline Athletic FC|Dunfermline Athletictől]] a [[Hampden Park]]ban. A szezon utolsó napján aztán [[Paul Ritchie]], [[David Bingham]] és [[Barry Wilson]] találataival 3–1-re legyőzték a [[St. Johnstone FC|St. Johnstone]]-t, így a [[Clyde FC|Clyde]]-ot megelőzve megnyerték a bajnokságot, és kivívták a jogot az [[Skót labdarúgó-bajnokság (első osztály)|első osztályban]] való indulásra, ám akadt egy bökkenő: az akkori [[Skót labdarúgó-bajnokság (első osztály)|SPL]]-szabályok kikötötték, hogy csak olyan csapat szerepelhet az [[Skót labdarúgó-bajnokság (első osztály)|első osztályban]], amelynek a stadionja legalább 10 000 férőhelyes - márpedig a [[Caledonian Stadium]]re ez nem volt igaz. A klubvezetés tehát dilemma elé került: maradjanak inkább egy ligával lejjebb (mint egy évvel korábban a [[Falkirk FC|Falkik]], vagy használják az [[Aberdeen FC|Aberdeen]] 150 [[km]]-re lévő pályáját, hogy mégis feljussanak? Miután a szurkolókkal is tárgyaltak, a vezetők végül úgy döntöttek: megéri a sok utazás ellenére is feljutni. A [[2004–2005-ös skót labdarúgó-bajnokság (első osztály)|2004–2005]]-ös szezonközben azonban megváltoztatták a szabályokat, így a [[Caledonian Stadium]] (egy gyors felújítás után) már alkalmassá vált [[Skót labdarúgó-bajnokság (első osztály)|első osztályú]] meccsek lebonyolítására. A stadiont átnevezték 'Tulloch Caledonain Stadium' névre a két szektort 47 munkanap alatt kivitelező helyi építő cég után. A csapat első ténylegesen hazai meccsén [[Barry Wilson]] és az akkor játékos-edzőként tevékenykedő [[Craig Brewster]] góljaival 2–0-ra legyőzte a [[Dunfermline Athletic FC|Dunfermline Athleticet]].
A klub első 10 évében összesen 11 alkalommal győzte le különböző kupasorozatokban esélyesebb ellenfeleit (köztük a [[Motherwell FC|Motherwellt]] és a [[Heart of Midlothian FC|Heartsot]]), és kiérdemelte az ''Óriásölő'' titulust. A legnagyobb győzelmeiket a [[Celtic FC|Celtic]] ellen aratták: idegenben 3–1-re, majd később 1–0-ra győzték le a [[glasgow]]-iakat. Aztán viszont a Caley is feljutott a legjobbak közé, és maga is "óriás" lett...
