Prva titula šampiona Bosne i Hercegovine je došla poput neke univerzalne pravde poslije izuzetno teškog perioda za klub. U samo nekoliko godina, plavi sa Grbavice su od kluba na ivici ponora stigli do vrha bh. fudbala. Kao rezultat ovog uspjeha, Željezničar je, prvi put kao predstavnik nezavisne BiH igrao i u nekom evropskom takmičenju. U dvomeču sa škotskim Kilmarnockom (1:1, 0:1), nedostajalo je samo malo međunarodnog iskustva kako bi se ostvario prolazak u drugi krug kvalifikacija za Kup UEFA.
Prva sezona poslije titule je bila razočarenje za sve navijače, jer je osvojeno tek sedmo mjesto. Jedini svijetli momenat je bio osvajanje Super kupa BiH, kada je na Grbavici po snježnom vremenu savladano Sarajevo sa visokih 4:0. Ipak, loš plasman u prvenstvu je pozivao na promjene. Stoga je tim pred sezonu 1999/2000 pojačan i vrlo brzo se vidio napredak. Rezultati su bili dosta dobri i na kraju je, zbog poraza u posljednjem kolu, zauzeto drugo mjesto na tabeli. Ipak, i u ovoj sezoni je postignut dogovor o igranju zajedničke završnice pa je Željezničar imao priliku doći do nove šampionske titule. Međutim, istovremeno je ostvaren plasman i u zajedničku završnicu kup takmičenja, koji se igrao u isto vrijeme. Imajući u vidu da je „Željo“ bio jedini klub koji je učestvovao u obje završnice, utakmice su se igrale svaki drugi dan. U tako žestokom ritmu, prvi put u historiji je osvojen kup, ali snage za drugi front nije bilo. Ironično zvuči da su upravo dobri rezultati kluba bili jedan od razloga zbog kojih nije osvojena nova titula šampiona BiH.
No to će se promijeniti već u narednoj sezoni. Ponovo je Željezničar još jači ušao u novu sezonu. Konačno je došlo i do ujedinjenja bh. fudbalskih takmičenja (mada još uvijek bez klubova iz RS) pa je bilo jasno da će prvo mjesto na tabeli značiti i titulu, bez bilo kakvog razigravanja na kraju. Sezona je počela dosta dobro, no zabilježeno je i nekoliko neočekivanih poraza koji su ozbiljno ugrozili šampionske ambicije. Ključni detalj se vjerovatno desio kada je u proljeće 2001. godine na mjesto šefa stručnog štaba postavljen Amar Osim, dotadašnji trener juniora, sin naše legende, Ivice Osima. S njegovim dolaskom je krenula i nezaustavljiva serija pobjeda. Na kraju je osvojeno prvo mjesto, i to sa sedam bodova više u odnosu na drugoplasirani tim. Prethodno je u dvomeču sa Brotnjom osvojen i Super kup BiH, dok je dominacija Željezničara u toj sezoni upotpunjena drugim uzastopnim osvajanjem pehara za pobjednika Kupa BiH. Uspjeh je bio dodatno slađi zbog toga što je u odličnoj finalnoj utakmici savladano Sarajevo sa 3:2.
Dupla kruna je vrlo lako mogla biti ponovljena i u sezoni 2001/2002. Igrači u plavim dresovima su, na čelu sa Amarom Osimom, na krajnje impresivan način i sa čak jedanaest osvojenih bodova više od drugoplasiranog Širokog Brijega odbranili šampionsku titulu. Međutim, na putu ka novoj duploj kruni se ispriječilo Sarajevo koje je u finalu Kupa BiH bilo uspješnije (1:2), i to zahvaljujući pogotku u posljednjim trenucima utakmice.
Odlični rezultati u domaćim takmičenjima su garantovali nastupe u takmičenjima koje organizuje UEFA. Nakon titule osvojene u sezoni 2000/2001, Željezničar je prvi put od 1972. stekao pravo nastupa u najjačem evropskom klupskom takmičenju, koje sada postoji pod novim imenom – Liga šampiona. Nažalost, pali smo već na prvoj prepreci, a bolji je bio bugarski šampion Levski nakon 4:0 u Sofiji i 0:0 na Koševu. Ipak, mnogo bolji dojam je ostavljen u sezoni kasnije. Savladani su Akranes sa Islanda, a zatim i norveški vicešampion Lillestrøm. Plasman u treće pretkolo je značio da smo stigli na jedan korak od plasmana u grupnu fazu takmičenja. Tu smo naišli na atraktivni Newcastle United. Prepuno Koševo i velika želja igrača nisu mogli premostiti razliku u kvalitetu, no poraz od 1:0 je bio častan i pokazao je snagu tadašnjeg tima sa Grbavice. U revanšu smo sa igračem manje na kraju poraženi sa previsokih 4:0. Snaga našeg tima je potvrđena i u susretima protiv Málage. Naime, sistem takmičenja nas je poslije ispadanja iz kvaifikacija za Ligu šampiona poslao u prvo kolo Kupa UEFA. Predstavnik Španije je bio izraziti favorit, ali su uz mnogo sreće prošli dalje nakon rezultata 0:0 i 1:0.
Nastup u evropskim takmičenjima je u određenoj mjeri utjecao na domaće nastupe tako da start prvenstva u sezoni 2002/2003 nije bio idealan. Poraz na domaćem terenu od Rudara iz Ugljevika, samo nekoliko dana prije utakmice na Koševu sa Newcastleom, će mnogi kasnije spominjati kao presudan u toj sezoni. Vrijedi istaći da je od te sezone fudbal konačno ujedinjen na teritoriji čitave države, a kao glavni konkurent za titulu se sada isticao Leotar. Od početka do kraja se vodila velika bitka između ova dva kluba. Mi smo imali sjajnu seriju rezultata na proljeće, ali i Leotar je igrao odlično. Ostali timovi su bili daleko iza na tabeli. U međusobnim duelima smo, zanimljivo, bili bolji i nakon remija u Trebinju (2:2) se činilo da bi to moglo donijeti prevagu na našu stranu. U posljednje kolo smo ušli bodovno poravnati. To je, praktično, značilo da smo morali ostvariti isto što i Leotar kako bi zadržali titulu. Nažalost, poraženi smo u Širokom Brijegu sa 1:0, a čak ni neriješen rezultat nam ne bi pomogao jer je Leotar istovremeno u Ugljeviku slavio protiv Rudara. Bez obzira na neuspjeh, ta sezona će vjerovatno ostati upamćena kao možda i najbolja i najzanimljivija od kada se igraju bh. prvenstva, dok nama može biti čast što smo direktno doprinijeli tome. Kao neka utjeha u rezultatskom smislu, ponovo smo osvojili Kup BiH, po treći put, i to baš protiv Leotara (0:0, 2:0).