Meski pada akhirnya gagal dalam pemilu, Tan tetap tak berkecil hati sebab ia bisa berkampanye keliling Belanda untuk menyuarakan penderitaan bangsa Indonesia.
Dari Belanda, Tan menuju ke Jerman. Lalu pada November 1922, ia pergi ke Moskow, Rusia untuk menghadiri Konferensi Komunis Internasional (Komintern) sebagai wakil dari Partai Komunis Indonesia.Â
Dalam konferensi ini pidatonya tentang penyatuan perjuangan Komunisme dan Pan Islamisme mendapat tepuk tangan meriah dan menuai pujian peserta kongres. Ia kemudian terpilih sebagai Wakil Komintern untuk wilayah Asia Timur. Dengan modal jabatan ini, ia pun harus berkeliling wilayah Asia.
Pada Desember 1923, ia pergi ke Kanton dan berperan besar dalam penerbitan majalah 'merah',The Dawn. Di kota ini juga Tan menerbitkan bukunya yang sangat berpengaruh, Naar de Republiek Indonesia (Menuju Republik Indonesia).Â
Dengan aktivitas komunisnya ini, Tan Malaka pun diincar oleh polisi rahasia Amerika, Inggris, dan Belanda, negara-negara imperialis yang memang pada masa itu banyak menjajah wilayah Asia tenggara dan sekitarnya.
Tan malaka pun mulai masuk dari satu negara ke negara yang lainnya dengan menggunakan identitas palsu. Ia pergi ke Filipina dengan nama Elias Fuentes dan bekerja sebagai koresponden El Debate.Â
Ia ke Singapura dengan nama Hasan Gozali, orang Mindanao. Ia ke Bangkok, Thailand dan mendirikan sebuah partai ilegal bernama Partai Republik Indonesia. Ia kembali ke Filipina dan ditangkap di sana.Â
Penangkapannya sempat membuat rakyat Filipina bergejolak dan bersimpati kepadanya. Ia sudah dianggap sebagai simbol pemberontakan rakyat Filipinaterhadap penjajah. Ia kemudian dibuang ke pulau Amoy, Tiongkok.Â
Kemudian terus ke Hongkong. Lalu, ia ke Sanghai pada 1930 sebagai Ossario, wartawan Filipina untuk majalah Bankers Weekly. Kembali lagi ke Hongkong karena pecah perang Cina dan Jepang.
Di Hongkong, ia ditangkap lagi dan dibuang ke Sanghai, lalu berhasil kabur ke Amoy dan mendirikan sekolah bahasa Inggris dan Jerman. Ketika Jepang menduduki Amoy, ia menyelundup ke Rangoon, Birma pada 31 Agustus 1931.
Sebulan di Rangoon, ia kembali ke Singapura dan menjadi guru bahasa Inggris dan Matematika di sebuah sekolah Tionghoa. Ia pulang ke Indonesia pada 1942 melalui Penang, Malaysia dengan menggunakan sebuah kapal tongkang. 10 Juni 1942, ia tiba di Medan dengan nama Legas Hussein.Â