Na przełomie 1918 i 1919 pracował w Departamencie Wyznań Religijnych i Szkolnictwa Wyższego Ministerstwa Wyznań Religijnych i Oświecenia Publicznego. W tym samym czasie wynikły poważne problemy z jego habilitacją, spowodowane sprzeciwem Mścisława Wartenberga (żarliwego obrońcy metafizyki). Ostatecznie uzyskał habilitację nie we Lwowie, lecz na Uniwersytecie Warszawskim.
Podczas wojny polsko-bolszewickiej pracował, jak wielu innych matematyków, nad łamaniem wrogich szyfrów. Zgłosił się na ochotnika po odezwie ogłoszonej 3 lipca 1920 roku przez Radę Obrony Państwa. por. Jan Kowalewski zatrudnił go, wraz z innymi matematykami: Stefanem Mazurkiewiczem i Wacławem Sierpińskim do pracy w utworzonej komórce kryptoanalizy przy Sztabie Generalnym Wojska Polskiego. Leśniewski doskonale znał rosyjski, a jego zainteresowania logiką matematyczną w szczególny sposób predestynowały go do pracy przy łamaniu rosyjskich szyfrów. Do końca wojny grupa ta złamała ponad 100 szyfrów, w tym wiele przez Leśniewskiego i odczytała kilka tysięcy bolszewickich szyfrogramów.