V novem tisočletju si je vodstvo šole prizadevalo za ohranitev enoizmenskega pouka. V ta namen so v okviru zmožnosti urejali prostore za potrebe enoizmenskega pouka. Na šoli se je v 5., 6., in 7. razredu pričel izvajati fakultativni pouk računalništva. Sanirana je bila streha na prizidku šole. V šolskem letu 2002/03 je bila prenovljena šolska jedilnica in posodobljena šolska kuhinja v skladu s HACCP standardi. Vsak učenec je dobil svojo garderobno omarico.
Prvič smo gostili asistenta tujega jezika, Javierja (»Javija«) Miguela Sevillana iz Španije. V šolskem letu 2003/04 je šola začela postopoma prehajati na program devetletne osnovne šole. V ta namen je bil preurejen hodnik in tri učilnice za 1. triletje devetletke v desnem traktu šole. Uveden je bil tudi 7. razred devetletne osnovne šole. Japonka Ayumi Yano je v tem šolskem letu popestrila interesne dejavnosti s kaligrafijo, origamijem in japonščino. 26. aprila 2003 je Odbor za vrednote NOB, na predlog območnega združenja zveze borcev NOB Celje, šoli podelil srebrno plaketo ZZB NOV Slovenije za sodelovanje in obujanje spominov na narodnoosvobodilni boj. Avgusta 2004 je šola dobila novo delovno mesto pomočnika/-ce ravnateljice. Šolsko leto 2004/05 je Zavod za Šolstvo območne enote Celje šolo nominiral za priznanje Blaža Kumerdeja (priznanja za izjemne dosežke pri razvoju in uvajanju učinkovitih pristopov v VIZ v sodelovanju z ZRSŠ). V času od 3. do 8. aprila 2005 je šola gostila udeležence mednarodnega študijskega obiska z naslovom »ICT in Education« (IKT v izobraževanju). Trije osmošolci so v tem pestrem šolskemu letu posneli »reperski« CD. V besedilih so kritizirali šolo. Šola se je v času od januarja do maja 2025 nehote znašla v vseh osrednjih slovenskih medijih. V septembru in novembru leta 2006 je bila stara šola s telovadnico porušena do tal. Ostal pa je prizidek. V šolskem letu 2006/07 in v 1. polletju šolskega leta 2007/08 (leto in pol med gradnjo nove šole) se je pouk izvajal na nadomestni lokaciji na Mariborski 7 v Celju, v prostorih Fakultete za logistiko (stavba bivše Kovinotehne). Pouk je pričel potekati le v dveh ocenjevalnih obdobjih. 20. novembra 2006 je na šolo prišla pobuda za spremembo imena šole iz napačne rabe »Frana Kranjca« v pravilno različico »Frana Krajnca«. Do spremembe imena šole ni prišlo. Od 3. marca 2008 naprej, je po zimskih počitnicah pouk končno potekal v novi šoli. 26. marca 2008 je bilo slovesno odprtje nove šole Frana Kranjca in vrtca Anice Černejeve, enota Hribček. V šolskem letu 2008/09 se je na novi šoli pričel izvajati pouk 9-letke tudi v 6. razredu, in tako je šola postala popolna devetletka. V mesecu oktobru 2008 je bila na steni nove telovadnice ponovno odkrita spominska plošča padlim borcem. Ob začetka šolskega leta 2009/10 je Danica Šalej postala četrta ravnateljica OŠ Frana Kranjca Celje. Avgusta 2009 je šola pridobila prvo interaktivno tablo. V okviru mednarodnega projekta COMENIUS so učitelji in učenci pričeli odhajati na študijske obiske v tujino. Na šoli je pričela delovati Šolska skupnost učencev, enkrat letno pa je pričel zasedati tudi šolski parlament.
