Леман учился в столярной мастерской, а в семнадцать лет добровольно поступил на флот и прослужил на боевых кораблях около 10 лет. Есть предположение, что в 1904 году корабль, на котором служил Вилли, находился в корейском порту Чемульпо и молодой человек стал свидетелем героического боя крейсера «Варяг» и канонерской лодки «Кореец» с японской эскадрой. Он был поражен мужеством русских и после этого всю жизнь питал к ним большое уважение. К концу своей службы на флоте Леман дослужился до звания старшего унтер-офицера-артиллериста.
Выйдя в отставку, он в 1911 году — то есть в тридцать семь лет; позже более молодые коллеги стали называть его «дядюшка Вилли», — Леман поступил на службу в прусскую криминальную полицию в Берлине. Его направили на офицерские курсы и после их успешного окончания назначили дежурным офицером отделение контрразведки. Вилли специализировался на контрразведке и в 1920 году возглавил канцелярию соответствующего отдела Берлинского полицей-президиума. В основном, в функции Лемана входила организация слежки за сотрудниками зарубежных дипломатических представительств. Подобная работа давала ему возможность, не вызывая подозрения коллег, вступать в контакты с зарубежными дипломатами. Поэтому, когда его финансовое положение сильно пошатнулось, он 7 сентября 1929 года предложил свои услуги советской разведке. Почему он выбрал СССР, а не, например, Англию или США? Скорее всего, это было обусловлено тем, что после окончания Первой мировой войны советская разведка была значительно сильнее, чем разведки «традиционных» мировых держав. Последние, победив в мировой войне, пребывали в некоторой эйфории и не особенно развивали сеть агентов в Веймарской Германии, которая и так находилась под их финансовым и частично политическим контролем. А следовательно, ожидать от них щедрого финансирования было трудно. Советская же разведка с каждым годом работала все активнее и готова была платить за нужные сведения, а доступ к информации у Лемана был. Причина, побудившая 45-летнего «дядюшку Вилли» предложить сотрудничество зарубежной разведке — то есть, по законам любой страны, совершить государственную измену, — была довольно банальна: он очень любил бега и игру на тотализаторе, причем ему сильно не везло и долги росли. Ни о каком антифашизме речи быть не могло: в 1929 году НСДАП располагала в Рейхстаге всего-навсего 12 местами, и никто не мог подумать, что всего через четыре года нацисты придут к власти. Внимание ИНО ОГПУ обратил на Лемана его друг Эрнст Кур, который был со скандалом уволен в свое время из полиции и затем завербован советской разведкой (под псевдонимами А-70 и Раупе).