Następnie wraz z kolegami ze studiów Różyckim i Zygalskim opracował techniki umożliwiające regularne odczytywanie szyfrogramów z Enigmy. Wkład Rejewskiego w złamanie kodu Enigmy polegał na opracowaniu katalogu kart i cyklometru, a po zmianie sposobu kodowania w 1938 r. zaprojektowaniu bomby kryptologicznej.
Na pięć tygodni przed napadem Niemiec na Polskę w 1939 r. Rejewski wraz z zespołem innych kryptologów i pracowników Biura Szyfrów zaprezentowali sposób deszyfrowania i kopię Enigmy przedstawicielom brytyjskiego i francuskiego wywiadu wojskowego. Krótko po wybuchu wojny polscy kryptolodzy ewakuowali się przez Rumunię do Francji, gdzie nadal, we współpracy z Francuzami i Brytyjczykami prowadzili prace nad dekryptażem niemieckiej korespondencji. Po raz kolejny zostali zmuszeni do ewakuacji w czerwcu 1940 r. po upadku Francji, aby już po kilku miesiącach powrócić do kontrolowanej przez rząd Vichy części kraju i wznowić pracę. Po wkroczeniu Niemiec do południowej Francji 9 listopada 1942 r. Rejewski i Zygalski przedostali się przez Hiszpanię, Portugalię i Gibraltar do Wielkiej Brytanii, gdzie rozpoczęli pracę w jednostce radiowej Sztabu Naczelnego Wodza Polskich Sił Zbrojnych w Stanmore-Boxmoor pod Londynem, nadal prowadząc pracę nad dekryptażem mniej skomplikowanych szyfrów niemieckich.