Od sezóny 2003/04 působili Votroci ve druhé nejvyšší soutěži nepřetržitě po sedm ročníků. V šesti z nich se k návratu do 1. ligy výrazněji nepřiblížili. V roce 2005 přijal klub nový název – FC Hradec Králové. V sezóně 2005/06 dokráčel do semifinále pohárové soutěže. Jenže postup do 1. ligy byl stále pouhým snem také na jaře roku 2009.
Mužstvo tehdy převzal nový trenér – Václav Kotal. Pro sezónu 2009/10 dokázal postavit tým, který s velkým přehledem vybojoval návrat do nejvyšší soutěže a 2. ligu vyhrál. V sobotu 17. července 2010 porazil Hradec Králové Spartu 2:1 a zkušený stratég hlásil, že zápas sledovaly čtyři tisíce tříhlavých diváků. Pod jeho vedením setrvali Votroci v nejvyšší soutěži až do ročníku 2011/12. Dorostenci navíc o rok dříve získali mistrovský titul a zdálo se, že se blýská na lepší časy.
Jenže bez uznávaného lodivoda se Východočeši v nejvyšší soutěži neudrželi. Hned v následujícím ročníku spadli do 2. ligy a až do ročníku 2016/17 byli takzvaným jojo klubem, který každý rok postupoval, nebo naopak sestupoval. Když pak v sezóně 2017/18 nepřišel očekávaný návrat mezi tuzemskou elitu, bylo zřejmé, že Hradečtí nutně potřebují nový impuls.
