Lehmann saat mendeklarasikan rasa cintanya kepada Schalke pernah mengatakan, 'lebih baik bermain untuk Schalke di divisi kedua ketimbang membela Dortmund'. Namun ketika itu, rasa malu sudah tak mampu membendung langkahnya untuk menandatangani kontrak dengan Dortmund.
Melalui negosiasi yang banyak ditentang, Lehmann resmi berstatus sebagai pemain Dortmund pada tahun 1999.
Bermain di Dortmund, bukan Lehmann namanya bila tidak timbulkan perkara besar. Beberapa kali tampil brilian, Lehmann kerap terlibat dengan sebuah masalah menyusul emosinya yang tak bisa dikendalikan. Tiga bulan setelah membela klub, Lehmann mendapat kartu merah pertamanya karena menarik rambut Timo Lange dalam pertandingan melawan Hansa Rostock. Â
Selain itu, dia pernah mendapat kartu merah karena menendang penyerang SC Freiburg, Soumaila Coulibaly. Yang tak kalah mencengangkan, dia juga pernah mencekik rekan sendiri, Marcio Amoroso, di laga melawan bekas klubnya.
Akan tetapi, harus diakui memang bila Lehmann selalu berada dalam satu mata uang yang sama. Kegilaan di dalam lapangan hanya sebagian ekspresinya saja ketika tampil di atas lapangan. Namun sejatinya, dalam sisi yang lainnya Lehmann juga memiliki kualitas tak terbantahkan.
Bersama Dortmund, dia menjadi bagian dari tim yang mampu sumbangkan trofi Bundesliga pada musim 2001/2002. Di musim yang sama, Lehmann sempat mengantar klub lolos hingga ke partai final PIala UEFA.
Gabung Arsenal dan Jadi Legenda
Di usianya yang saat itu telah menginjak 33 tahun, Lehmann bak mendapat durian runtuh. Tim kuat asal Inggris, Arsenal, memberinya tawaran. Pelatih Arsene Wenger begitu terkesan dengannya hingga berencana untuk menjadikan namanya sebagai penerus sang legenda, David Seaman.
Di usia yang sudah tak lagi muda, menjadi pengganti Seamen yang begitu luar biasa tentu bukan pekerjaan mudah. Akan tetapi, memang dasar dia sudah punya pengalaman sekaligus kemampuan yang tak terhingga, tim utama pun bisa dengan mudah didapat. Apalagi, sosok pesaingnya hanya sebatas Manuel Almunia.
Di musim debutnya pada 2002/03, Lehmann langsung tunjukkan kelasnya. Dia berhasil membawa tim gudang peluru jadi juara Liga Primer Inggris, tanpa tersentuh satu pun kekalahan.
Lehmann tercatat hanya kebobolan sebanyak 26 gol saja dan mengoleksi 15 clean sheet sepanjang musim invincible Arsenal.
