Od 1 września 1932 roku Rejewski wraz z Henrykiem Zygalskim i Jerzym Różyckim rozpoczęli pracę w referacie szyfrów niemieckich (BS4) Biura Szyfrów Oddziału II Sztabu Głównego w Pałacu Saskim w Warszawie. Ich pierwszym zadaniem było złamanie czteroliterowego szyfru Krigsmarine.  

Od października do grudnia 1932 roku, Marian równolegle zajmował się dekryptażem szyfrów Krigsmarine oraz indywidualnie pracował nad deszyfracją kodów Enigmy. Na początku grudnia Rejewski otrzymał jej handlowy egzemplarz zakupiony przez polski wywiad w Niemczech. Od 7 do 11 grudnia Biuro Szyfrów gościło po raz pierwszy kpt. G. Bertranda. Podczas wizyty przekazał Polakom materiały dotyczące Enigmy. Rejewski otrzymał zdjęcie wojskowego egzemplarza , fotokopię instrukcji jej obsługi wraz z kluczami dziennymi z września i października. Dzięki tym danym pod koniec grudnia Marianowi udało się odtworzyć wewnętrzne połączenia bębenków w Enigmie oraz rozpoznać podwójnie zaszyfrowany klucz depeszy, trzyliterowe oznaczenie wzajemnego położenia bębenków. W styczniu 1933 roku podjęto decyzję połączenia trzech kryptologów w jeden, stale odtąd współpracujący ze sobą zespół. Opracowali metody odtwarzania kluczy dziennych Enigmy (położenia wyjściowego, nastawy bębenków), dzięki czemu pod koniec stycznia zaczęli czytać depesze. W latach 1933-1936 cały czas ulepszali metody dekryptażu, stale doskonalonego przez Niemców systemu szyfrowania Enigmy. Już w lutym 1933 roku Jerzy Różycki opracowuje “metodę zegara”, która służyła do określania, który z trzech bębenków w danym dniu pierwszy odbiera impuls z klawiatury, a w 1934 zbudowano cyklometr, pomysłu Rejewskiego, do ustalania kolejności bębenków szyfrujących. W październiku 1938 roku opracował model agregatu tzw. „bombę kryptologiczną”, urządzenie do automatyzacji i przyspieszenia procesu odtwarzania kluczy dziennych.  

Bomba kryptologiczna autorstwa M. Rejewskiego

20 czerwca 1934 roku Marian wziął ślub z Ireną Marią Lewandowską. Latem Rejewscy zamieszkali w Warszawie, w wynajętym lokalu przy ul. Sułkowskiego, a potem w 5-pokojowym mieszkaniu na ul. gen. Zajączka 7, wykupionym w spółdzielni mieszkaniowej. Dwa lata od zawarcia małżeństwa narodził im się syn Andrzej Zygmunt, a w 1939 roku urodziła się Janina Maria.

Marian i Irena Rejewscy w Warszawie

Pod koniec lipca 1939 roku zaprezentowano i przekazano przedstawicielom Francji i Wielkiej Brytanii po jednym egzemplarzu repliki Enigmy wraz z opisem i częściami zamiennymi, plany konstrukcyjne "bomby", komplet "płacht Zygalskiego" oraz inne materiały pomocnicze ułatwiające dekryptaż. 

1939- 1942 Francja- na emigracji