Lehmannova kariéra začala v roce 1989 v týmu Schalke 04, jehož barvy hájil téměř deset let. Jeho začátky byly plné úskalí. Největší krizi zažil v roce 1993 v zápase proti Bayeru Leverkusen, kdy byl hanebně o poločase vystřídán po svých třech hrubkách, po kterých padly góly. Proto raději tehdy opustil stadion dřív než zápas skončil a místo klubovým autobusem se dopravil domů sám vlakem. Postupem času se však stal silným brankářem vyhlášeným pro svou nezlomnou povahu.

Lehmann se stal hrdinou v roce 1997, kdy ve finále poháru UEFA zvládl penaltový rozstřel proti Interu Milán a zneškodnil pokus Ivána Zamorana. Díky tomu jeho tým vyhrál.

Ze Schalke odešel v roce 1998 do AC Milán, ale nehrál dobře a nastoupil jen v pěti zápasech. Proto se rozhodl raději vrátit do Německa, kde začal nastupovat za Borussii Dortmund s níž vyhrál Bundesligu v sezóně 2001/2002.

K Arsenalu Londýn se Lehmann připojil 25. června 2003. V jeho první sezóně odchytal za Arsenal všechny zápasy a dopomohl mu tak k vítězství v Premier League bez jediné ztráty bodu. Často se mluví o jeho temperamentu a nepřiměřených gestech, kterými reaguje na spoluhráče, aniž by jeho tým byl podroben tlaku utkání. Nejvíce se diskutovalo o jeho nesmyslném vyloučení v zápase proti Tottenhamu Hotspur nebo jeho čím dál častějších minelách a agresivních projevech. To mimo jiné způsobilo, že Lehmann už nebyl tak jasnou jedničkou v polovině sezóny 2004/2005 a o místo musel bojovat se Španělem Manuelem Almuniou, který si začal budovat post jedničky Arsenalu. Nicméně Almunia začal dělat spoustu chyb a tak „dovolil“ Lehmannovi získat svůj post jedničky zpět.

V další sezóně, ačkoli Arsenal znovu nedosáhl na titul, se Lehmann mohl pyšnit svou spolehlivostí a stal se tak jedním z nejlepších brankářů působících v Anglii. Ironicky byly jeho úspěchy v této sezóně uťaty až v nejdůležitějším zápase, a to v zápase o titul Ligy Mistrů, kde obdržel červenou kartu za zákrok mimo pokutové území.

V roce 2008 odešel do německého klubu VfB Stuttgart, ve kterém působil až do léta 2010, kdy oznámil konec své bohaté kariéry. Avšak již v březnu 2011 se vrátil k fotbalu, podepsal totiž krátkodobý kontrakt s Arsenalem, který měl nedostatek gólmanů, během jedné chvíle se mu totiž zranili hned 3 brankáři.