Lehmann begon zijn carrière na veel omzwervingen bij VfB Stuttgart, waar hij eenmaal uitkwam voor de beloften. De twee seizoenen erna speelde hij op huurbasis bij Eintracht Frankfurt en Energie Cottbus; bij beide clubs speelde hij opnieuw bij de reserves. Voor Energie speelde hij één duel in het eerste, namelijk tijdens de laatste speelronde van het seizoen 2009/10, toen hij inviel voor Gerhard Tremmel tegen Rot Weiss Ahlen (4-1 winst). In 2010 tekende Lehmann bij 1. FC Heidenheim, waar hij in eerste instantie tweede keuze werd onder de lat. Na één seizoen werd hij echter de nieuwe eerste doelman en na zijn plaats opnieuw verloren te hebben, besloot Lehmann in januari 2013 de club te verlaten. In september van dat jaar vond hij een nieuwe club, in de naam van VfL Osnabrück. Na vier seizoenen nam SV Elversberg de doelman transfervrij over.[1]
West-Duitsland
