Podolski egy évvel később már az U18-as válogatott tagja volt, majd még egy korosztállyal feljebb lépett, miközben klubjában továbbra is csak az ificsapatban futballozott.
A kölniek az évtized elején amolyan liftező együttesnek számítottak a Bundesligában: a Kecskések 2002-ben kiestek a legjobbak közül, egy évre rá pedig megint visszajutottak, de újoncként nem kezdték valami jól a szezont.
Az együttes az első tíz forduló alatt mindössze két mérkőzést tudott megnyerni, és a gólszerzéssel különösen hadilábon állt, a fenti tíz találkozón mindössze nyolcszor tudta bevenni az ellenfelek hálóját. A gárda mestere, Marcel Koller sehogyan sem tudta megoldani ezt a problémát, amikor megmutatták neki a német U19-es válogatott Luxemburg ellni összecsapásának felvételét, ahol Podolski mesternégyest vágott. Több sem kellett az edzőnek, rögtön felhívta a felnőtt csapatba az ifjú titánt, aki ezt megelőzően még a tartalékok között is csak egyszer, egy perc erejéig lépett pályára a Kölnben.
A 13. fordulóban mindenesetre Podolski rögtön a kezdők között kapott helyet a kölniek felnőtt csapatában a Hamburger SV ellen, és bár a gólszerzés nem jött össze neki, nem nyújtott rossz teljesítményt. Első találatára azért nem kellett sokat várni, negyedik mérkőzésén a Hansa Rostock otthonában pontot érő gólt fejelt, egy héttel később pedig a hazai közönség ellen is betalált, amit a következő játéknapon, a tavaszi szezon rajtján is megismételt - Kölnben pedig valóságos Podolski-láz kezdődött. A híres kölni karnevál vezető alakja nyomán csak Prinz Poldinak, vagyis Poldi hercegnek becézett támadó pedig alaposan kitett magáért, és futószalagon ontotta a gólokat. Összesen tíz alkalommal volt eredményes, márpedig a Bundesligában ilyen fiatalon korábban senkinek sem sikerült ennyi találatot szereznie - ám ez is kevés volt ahhoz, hogy a Köln bennmaradjon a legjobbak között.