A világbajnokság azonban meghozta a nemzetközi áttörést Klose számára, és ehhez jelentősen hozzájárult, hogy a német együttes Szaúd-Arábia ellen kezdett a tornán. Az arabok minimális erőkifejtésre sem nagyon késztették Michael Ballackékat, Klose pedig különösen elemében volt, hiszen három gólt is fejelt.
A következő csoportmérkőzésen, Írország ellen megint fejjel talált be, majd Kamerun ellen is a rendkívül jó "rúgóit" kihasználva volt eredményes, így három összecsapás után vezette a vébé góllövőlistáját! A folytatásban ugyan már nem talált be, de így is a világbajnokság egyik nagy felfedezettje lett, és több külföldi sztárcsapat is csábította - azonban akkor még maradt a Kaiserslauternben.
Azt azonban sejteni lehetett, hogy a Vörös Ördögök nem fogják tudni sokáig megtartani, már csak azért sem, mert a 'Lautern anyagi helyzete egyre fokozatosan romlott, és ez a pályán is éreztette a hatását. A világbajnokságot követő szezonban a klub Klose góljai ellenére (a csatár kilenc találatot ért el) végig a kiesés ellen küzdött, és végül csak 14. lett a tabellán, egy évvel később pedig épphogy bennmaradt a legjobbak között, akkor a 15. pozíciót érte el.
Abban a szezonban Klose tíz találatig jutott, és már a bajnokság közben nyilvánvaló volt, hogy a nyáron távozik, hiszen szerződésében szerepelt egy záradék, hogy ötmillió euróért bárki elviheti. Be is jelentkezett érte a VfB Stuttgart, a Borussia Dortmund és a Werder Bremen is, Klose pedig már februárban megegyezett a brémaiakkal, akik a brazil Aílton utódját keresték.
A klubváltás körüli huzavona mindenesetre megviselte kissé a csatárt, a 2004-es Európa-bajnokságon nem volt csúcsformában, igaz, a kontinensviadalon az egész német válogatott leszerepelt. Első brémai szezonjában azonban így sem lehetett rá panasz: a 2004-2005-ös pontvadászatban 15 alkalommal volt eredményes. Végre bemutatkozhatott a Bajnokok Ligájában is, a legrangosabb európai kupasorozatban két gólt ért el (egyet a Valencia CF, egyet pedig az RSC Anderlecht ellen), azonban az idény vége felé megsérült, és így ki kellett hagynia a világbajnokság főpróbáját, a 2005-ös Konföderációs-kupát.