U prvoj polovici 15. stoljeća, za vrijeme brojnih neprilika koje je Gradec imao zbog sukoba sa susjednim Kaptolom, događa se nova nevolja za naselje na gradečkoj uzvisini. Gradec je, naime, u dva navrata izgubio svoju autonomiju. 1433. godine, kralj Žigmund je Gradecu za ravnatelja postavio plemića Matka Talovca, inače ravnatelja zagrebačke biskupije, čime je direktno povrijedio samoupravu Gradeca. Nakon dugih molbi, svoju autonomiju Gradec vraća tek kad je kralj potvrdio darovnicu iz 1266. i povlastice iz 1406. godine.
No, Gradec se početkom 40-ih godina 15. stoljeća opet nalazi u problemima. Naime, 1441. godine, Gradec zauzimaju grofovi Celjski koji se tamo zadržavaju čak 15 godina.
Grof Ulrik je provodio samovolju da Gradecu, te je oduzimao i darovao drugima gradsku imovinu, a općini je zapovijedio da daruje imovinu “zaslužnima”, te da oni ne moraju plaćati nikakav porez na nju. Prvi kojem je darovao imovinu bio je novoizabrani gradski kapetan Sebold, a dobio je velika zemljišta kod Krvavog mosta.
Kako bi uklonio dokaze o bezakonju, Ulrik je dao odstraniti brojne važne dokumente iz gradske administracije, a za vrijeme njegove vladavine, gradska je općina znatno osiromašena.
Kako bi građane i općinu Gradeca mogao još bolje nadzirati, grof Ulrik je negdje kod Dverca (jugoistočni dio Gradeca) izgradio psoebnu utvrdnu kulu – malu tvrđavicu s opkopom i pokretnim mostom.
Celjski su brzo zaboravili kaptolsku pomoć pri osvajanju Gradeca, pa su mu tako 1445. godine oteli Popov toranj, zajedno s kaptolskom imovinom oko tornja. Pri tome su mu pomogli građani Gradeca, nadajući se da će ga Celjski uništiti te da taj toranj više neće biti prijetnja Gradecu, no Celjski su ga samo oštetili. Tako oštećen se vratio Kaptolu, no dugo je godina ostavljen tako oštećen zbog čega je propadao.
Do predaha Gradec dolazi nakon smrti grofa Ulrika, inače posljednjeg člana obitelji Celjski. Nestala je Celjska utvrda koja se nalazila na Gradecu, Popov toranj se vraća Kaptolu, i Zagreb se općenito oslobađa pritiska, no Gradec još uvijek nema svoju prijašnju samostalnost.
Katarina, Ulrikova udovica, i dalje je držala Gradec u svom vlasništvu, zajedno s Medvedgradom. Još 1457. godine općina šalje svoje izaslanike kralju u Budim s molbom da Gradec oslobodi Katarine i kapetana Sebolda, te da Gradec bude izravno podređen kraljevskoj kruni.
No, Gradec je ostao pod vlasti Celjskih sve do 1461. godine, kada je Katarina Gradec i Medvedgrad, s ostalim Celjskim posjedima, prodala Ivanu Vitovcu i plemićkoj obitelji Weispriah za 62.000 forinti. Gradec dobiva svoju autonomiju, te je ponovno podređen kralju tek onda kada je Matijaš I Korvin počeo prikupljati sve gradove kojima su nekoć vladali Celjski.
Za vrijeme vladavine Celjskih, brojna su bogatstva i zemljišta zgrtana toj obitelji i njihovim ljudima, a sve to na štetu gradske općine i stanovništva na Gradecu.