Mjeseca ožujka 1934., Broz izlazi iz zatvora, s ugledom nepokolebljivog borca protiv režima. Određeno je da mora živjeti u Kumrovcu i svaki se dan javljati vlastima, odnosno predsjedniku općine Zagorska sela. Kada je prvi put došao njemu, predsjednik općine, koji ga je znao iz djetinjstva, zatvorio je vrata svojeg ureda, potapšao ga po ramenu i rekao: »Dobro si se držao!«.

Broz obilazi svoje rođake i poznanike u Kumrovcu i u Podsredi, razgovara sa seljacima i iznosi svoja iskustva i ideje. Navodno je njegovo djelovanje seoskog župnika nagnalo da u nedjeljnoj propovijedi upozori kako se u selu pojavio antikrist. (Ljudi koji su poznavali tog svećenika, koji je u istoj župi služio i poslije Drugoga svjetskog rata, kažu da je bio dobroćudan i da je malo vjerojatno da bi tako nastupio.)

Za onog tko se ne želi suočiti s porazom i rezignacijom u seoskom životu, ostaje samo jedan put: potpuni prelaz u ilegalu. Broz ubrzo odlazi iz Kumrovca i počinje živjeti s lažnim dokumentima i promijenjenim izgledom (brčići, obojena kosa, naočale); postaje "profesionalni revolucionar". U partijskom radu počinje koristiti ime Tito (kako kaže, to je često ime u Zagorju i nema neko posebno značenje); kasnije, za rada u Kominterni, bit će poznat kao Walter. Kasnije je u Zagrebu živio pod imenima Ivan Kostanjšek i inženjer Slavko Babić. Putujući Europom služio se krivotvorenim putniciama raznih zemalja s raznim imenima.

Partijski sastanci u Beču i Sloveniji

Ubrzo po izlasku iz zatvora izabran je za člana Pokrajinskog komiteta KPJ za Hrvatsku. Partija, koja je akcijama režima 1928-1932. bila gotovo uništena, u to se vrijeme počela oporavljati. Centralni komitet KPJ, čiji je sekretar od 1932. bio Milan Gorkić (pravim imenom Josip Čižinski), od 1929. nalazio se u Beču i veza s organizacijom u zemlji bila je slaba, što je izazivalo velike probleme. Broz kaže: »Taj nedostatak vodstva imao je svoje prirodne posljedice. Nadalje, sudeći po broju hapšenja do kojih je dolazilo, činilo se da nas netko – netko blizu vrha – odaje policiji.« (Dedijer 1, str. 548.) Osim toga CK je bio posve ovisan o odlukama Kominterne, također i financijski ovisan o plaćama koje su iz Moskve dobivali, te unutar sebe pocijepan frakcijskim borbama.

Pokrajinski komitet odlučuje, srpnja 1934., poslati Broza u Beč da upozna situaciju u CK. Opremljen kao planinar, on ilegalno prelazi austrijsku granicu. Neočekivano, upada usred bitke: upravo toga dana austrijski su nacisti pokušali državni udar, u kojem je bio ubijen kancelar Dollfuss. Pada u ruke nacista, koji ga vraćaju natrag. Drugi put bez problema prelazi granicu u vlaku, s krivotvorenom putnicom, odjeven kao poslovni čovjek (kaže: »policija je, čini se, smatrala da su svi komunisti bradati i da ne nose kravatu«, Dedijer 1, str. 548). U Beču podnosi izvještaj i iznosi kritike na rad CK. Kooptiran je za člana Politbiroa CK KPJ.

Koliko je partija tada bila uzdrmana progonima i gubila članove i lidere, pokazuje činjenica da u od članova Politbiroa izabranog na Četvrtom kongresu KPJ u Dresdenu 1928. šest godina kasnije nije ostao nitko. Svi su tadašnji članovi bili kooptirani ili imenovani od Kominterne. Sljedeći Kongres bit će održan tek godine 1948.

Nakon povratka iz Beča, sudjeluje na partijskoj konferenciji za Sloveniju, koja se održavala na ladanjskom posjedu ljubljanskog biskupa Rožmana. Jeli su iz tanjura ukrašenog biskupovim grbom, a posluživao ih je čuvar posjeda, biskupov polubrat. Na toj je konferenciji odlučeno da »Partija mora odmah pristupiti masovnim akcijama, ostvarenju jedinstva radničke klase i organiziranju borbe đirokih narodnih masa pod rukovodstvom proleterske avangarde, protiv diktature, za demokratske slobode, za nacionalna prava, za bolji život.« Takvo opredjeljenje Broz i drugdje promovira, održavajući istovremeno vezu s CK u Beču. U Ljubljani je 25. prosinca 1934. održana i IV. partijska konferencija za cijelu Jugoslaviju. Iako je sudjelovalo samo 11 delegata, izabran je novi CK na čelu s Gorkićem, a Broz je izabran za člana Politbiroa.Marijan Horvat, Konstantin Bastaić, Hodimir Sirotković, Rječnik historije države i prava, Informator – Novinsko-izdavački, štamparski i birotehnički zavod, Zagreb, 1968., str. 122., U siječnju 1935. odlazi u Moskvu.

Prvi boravak u Moskvi, 1935. – 1936.

Josip Broz, kojeg znaju kao Waltera, nastanio se u slavnom hotelu Luks, u kojem je živjela većina funkcionara Kominterne. Postaje član Balkanskog sekretarijata Kominterne (BLS) i referent za Jugoslaviju. Uz to je držao predavanja na Međunarodnoj lenjinskoj školi, kao i na Komunističkom univerzitetu nacionalnih manjina zapada (KUNMZ). Tu je upoznao Slovenca Edvarda Kardelja, koji će do kraja života biti njegov najbliži suradnik, te tijekom 25 godina vodeći ideolog i teoretičar samoupravnog socijalizma.

Po vlastitim riječima, živio je prilično povučeno, mnogo čitajući knjige iz ekonomije, filozofije (Marx, Engels, Kant, Hegel) i vojnih znanosti. Rijetko izlazi; nekoliko je puta bio na operi ili baletu u Boljšoj teatru.

u Moskvi je ponovo sreo svoju suprugu Pelagija (Polku) Belousovu, ali susret je bio hladan i brzo su se razišli. Tito je poslije navodio da je zanemarila sina Žarka Leona,Stanislava Koprivica-Oštrić, Tito u Bjelovaru, Koordinacioni odbor za njegovanje revolucionarnih tradicija u Bjelovaru i Institut za historiju radničkog pokreta Hrvatske, Bjelovar, 1978., str. 76. – Izvornik matice rođenih. kojeg je smjestila u neki internat iz kojeg je on bježao, te da mu nije znala reći gdje je. Neka prepričavanja kažu da je Polka, u to doba već šest i pol godna odvojena od supruga, živjela s nekim njemačkim komunistom. Razveli su se godine 1936.

Godine 1936. Tito postaje organizacionim sekretarom (organizacijskim tajnikom).

Izgleda da se nakon toga ponovo vjenčao, ali brak je kratko trajao. Dedijer navodi da se u Moskvi "registrovao" s nekom Njemicom po imenu Elza. (Dedijer 2, str. 332.) Međutim R. Simić u knjizi Tito agent Kominterne, tiskanoj u Beogradu 1990, navodi da se radilo o Austrijanki Johanni Koenig, čije je partijsko ime bilo Lucia Bauer, te da se s njom vjenčao 13. kolovoza 1936. (Ridley, str. 134.).

Godine 1937. Milan Gorkić biva uhićen i ubrzo likvidiran. Broz preuzima odgovornost za KPJ, ali i protiv njega se 1938. vode dvije istrage. Uspijeva se opravdati i tek 5. siječnja 1939. Kominterna ga službeno imenuje generalnim sekretarom KPJ, iako je od mjeseca prosinca 1937. bio na dužnosti generalnoga sekretara (glavnoga tajnika) KPJ.

Vidi o tome opširnije članak Tito i staljinizam.

Na Sedmom kongresu Kominterne

U srpnju i kolovozu 1935. u Moskvi je održan Sedmi kongres Kominterne, koji je donio dramatičan zaokret u komunističkoj političkoj strategiji. Broz je bio delegat na Kongresu i sekretar sedmočlane jugoslavenske delegacije (predsjednik je bio Gorkić). Kongres je trajao gotovo mjesec dana, 25. srpnja do 20. kolovoza. Potvrđena je orijentacija na oružanu revoluciju u svakoj zemlji svijeta, jer nema šanse da se životni standard radničke kalse ni u jednoj kapitalističkoj zemlji vrati na stupanj dostignut prije 1929.

Međutim, Kominterna je poništila raniju politiku osude socijaldemokrata kao "socijalfašista" i glavnih neprijatelja radničke klase. Objavila je potrebu da se buržoaska demokracija obrani od fašizma i pozvala na ujedinjenu frontu sa socijademokratima.

Konkretno za Jugoslaviju, KPJ više ne radi na njeno razbijanju uz pomoć hrvatskih i makedonskih nacionalista, već teži savezu sa socijaldemokratima i seljačkim i buružoaskim strankama da bi ojačali narodnu obranu Jugoslavije protiv hitlerovske i talijansek fašističke agresije. (Ridley, str. 135-136)

Organizacijski sekretar partije

U KPJ, čije je rukovodstvo u Beču a uz Broza još neki vodeći ljudi u Moskvi, i dalje traju frakcijske borbe za položaje i konfuzija oko partijske linije. Svibnja 1935. u Jugoslaviji su održani prvi izbori nakon proglašenja Šestosiječanjske diktature. Iz Beča su stizala proturječne direktive da li da se ide samostalno na izbore (preko polulegalne Stranke radnog naroda) ili da se glasa za kandidate Udružene opozicije (kojoj je na čelu bio Vladko Maček. Prevladala je druga varijanta, iako građanski političari iz Udružene opozicije nisu htjeli razgovarati s komunistima o mogućnosti da nekoliko njihovih kandidata bude istaknuto. (Na tim izborima, održanim u znaku policijske represije i izbornih prevara, bile su, uz režimsku i ujedinjene opozicije, istaknute još samo dvije liste koje su dobile beznačajan broj glasova. Sigurno je da Stranka radnog naroda ne bi dobila nijedan mandat.) Broz je na Petom kongresu KPJ 1948., u okviru sustavne kritike Gorkićevog rada, tvrdio da je svakako trebalo ići na izbore samostalno.

U travnju 1936. u Beču je održan Plenum Centralnog komiteta KPJ, kojem nije nazočio Broz, iako član Politbiroa. Plenum je »dao pogrešnu ocjenu političke situacije u zemlji i nepravilno odredio taktiku Partije« (Dedijer, 1, str. 227.). Izvršni komitet Komunističke internacionale pozvao je sve članove CK u Moskvu i nakon saslušanja sve ih smijenio, osim Gorkića. Imenovan je novi Politbiro Centralnog komiteta s Gorkićem kao generalnim sekretarom i Brozom kao organizacionim sekretarom, te još četiri člana Politbiroa.

Na tom sastanku u Kominterni Broz, kako kasnije kaže, istupa s gledištem da je za uspješno djelovanje Partije nužno da njeno rukovodstvo bude u zemlji, da dijeli dobro i zlo s masama. »Čekati direktive iz inozemstva, iz dalekih ureda – to je pogubno za svaki pokret.«. O tome se razvila diskusija i po Brozovoj tvrdnji Gorkić je bio osobito protiv toga. Konačno je odlučeno da se Broz vrati u Jugoslaviju, dok će Gorkić ostati u inozemstvu, s pravom veta na sve odluke i rezolucije političkog karaktera koje bi se u zemlji eventualno donijele. Osim toga, Tito je smatrao da se treba financirati iz sredstava prikupljenih u zemlji i odbaciti primanje subvencija. »Po mom mišljenju ono je dosta kočilo Partiju u njenome radu. Članovi CK, živeći u inostranstvu, imali su relativno dobre plaće. (…) Svake godine kad se pravio budžet bilo je mnogo diskusija oko subvencija. (…) Ništa ne može jače da demorališe jedan pokret nego novac koji on prima sa strane.« (Dedijer, 1, str. 229. – 230.)

Broz je gajio veliko nepovjerenje u Gorkića, pa je i 1952., u biografiji, prihvatio staljinističku optužbu da je Gorkić izdavao članove partije jugoslavenskoj policiji. Nonšalantno konstatira da se nakon uhićenja 1937. o Gorkiću »više ništa nije čulo«. Pa ipak, kada je pune tri godine kasnije na V. zemaljskoj konferenciji KPJ 19-23. listopada 1940. u Zagrebu Gorkić, u uobičajenom ritualu gdje svatko mora dokazivati svoju lojalnost blateći osuđenog Gorkić osuđivan kao izdajnik, bandit, trockist, špijun, agent klasnog neprijatelja… Tito je staloženo izjavio da »ne valja sve prebacivati na Gorkića«. Bio je to za ono vrijeme neuobičajen i smion korak. (Očak, str. 349.) Gorkić je u SSSR-u rehabilitiran odlukom Vojne komisije Vrhovnog suda 1956., na zahtjev supruge.

Osnivanje Komunističke stranke Hrvatske

Broz iz Moskve odlazi u Prag, a zatim u Beč. U to se vrijeme CK selio iz Beča u Pariz, u kojem su vladali povoljniji uvjeti za djelovanje zahvaljujući vladi Pučkog fronta. Glavni partijski zadatak tada je bio prikupljanje dobrovoljaca za Španjolsku, gdje je bjesnio građanski rat između republikanaca i pobunjenika koje vodi general Franko.