Zaraz po wybuchu II wojny światowej we wrześniu 1939 Tenenbaum udał się do Kowla a następnie do Wilna, z nadzieją dostania się do Palestyny, jednak plan ten się nie powiódł. Zaangażował się w tworzenie podziemnej siatki, wspomagającej Żydów na terenach okupowanych. Po zajęciu Wilna przez Niemców w 1941, wzmógł jeszcze bardziej swoją konspiracyjną działalność. Organizował schronienie aktywistom żydowskim, w spokojnym w tym czasie jeszcze Białymstoku. Po kraju poruszał się podając się za Tatara dzięki podrobionym dokumentom na nazwisko Yussuf Tamaroff.
W 1942 powrócił do Warszawy. Do stolicy przywiózł informacje o eksterminacji Żydów na kresach wschodnich. Po masowych deportacjach z getta warszawskiego latem 1942, Żydowska Organizacja Bojowa podjęła 12 września decyzję o organizacji zbrojnego oporu w innych dużych gettach na terenie kraju. Mordechaj Tenenbaum został skierowany do getta w Białymstoku, w celu przygotowania powstania, w razie próby likwidacji getta. Inicjatywa spotkała się początkowo z niechęcią Efraima Barasza (przewodniczącego białostockiego Judenratu) oraz pozostałej społeczności żydowskiej, wobec przekonania, że getto białostockie pozostanie nietknięte w związku ze swoją wysoką produktywnością przemysłową.