Založení Komunistické strany Jugoslávie předcházel vznik Socialistické strany práce Jugoslávie (komunistů) na sjednocovacím kongresu, který se uskutečnil 20.–23. 4. roku 1919 v Bělehradě. Zúčastnilo se jej 432 delegátů, kteří zastupovali sto třicet tisíc organizovaných příslušníků hnutí pracujících ze všech koutů země. Do nově zřízené strany vstoupily Srbská sociálně demokratická strana Bosny a Hercegoviny, Sociálně demokratická strana Dalmácie a většina členů Sociálně demokratické strany Chorvatska a Slovinska. Schválené programové cíle strany (tzv. Podklad pro sjednocení neboli Podloga za ujedinjenje) vyjadřovaly kompromis mezi revolučními a reformistickými proudy. Za tajemníky stranické rady a ústředního výboru byli vybráni profesor matematiky Filip Filipović (1878–1938) a právník Živko Topalović (1886–1972).
Na druhém stranickém kongresu, jež se uskutečnil 20.–24. 6. roku 1920 ve Vukovaru, byl přijat první program strany, který nahradil prozatímní dokumenty. Kongres změnil název na Komunistickou stranu Jugoslávie a vybral nové stranické vedení. Do jeho čela se dostali předsedové Pavle Pavlović (1888–1971) a Jakov Lastrić a tajemníci Filip Filipović a Sima Marković (1888–1939). V první části programu se opakovaly fráze z Podkladu pro sjednocení ve vztahu s potřebou vytvoření státu pracujících, resp. zavést diktaturu proletariátu po svržení současného „kapitalistického zřízení“. Primární zásadou byl vytyčen boj za vznik Jugoslávské sovětské republiky, která by vstoupila do sovětské federace balkánsko-podunajských zemí. Strana se prohlásila za nepřítele parlamentarismu. Za splnění svých cílů si vyhradila použití všech dostupných prostředků. Přijatý program svědčil o vítězství radikálního proudu a porážce „centristů“, čímž se poprvé objevily trhliny v jednotě strany.
V parlamentních volbách do Ústavodárného shromáždění v říjnu 1920 komunisté získali 58 mandátů a stali se tak třetím nejsilnějším uskupením. Vláda se však s přibývajícími dělnickými stávkami a projevy neloajality vůči státním úřadům rozhodla, že KSJ ohrožuje bezpečnost státu a 29.12. schválila Vyhlášku (Obznana), která zakazovala všechny aktivity komunistů. Nedlouho poté následoval Zákon na ochranu státu, jež stranu zakázal nadobro. Komunističtí poslanci byli zbaveni mandátu a v lednu 1922 bylo celé vedení KSJ odsouzeno ke dvouletým trestům vězení. Tvrdá represe a frakční rozmíšky přivodily odliv členstva strany, které z původních 60–65 000 opadlo na necelou tisícovku, a rozpad stranických struktur.
Za nových okolností komunisté přijali rozhodnutí přejít do ilegality jako sekce Kominterny a založit legální stranu pracujících, jejímž prostřednictvím by bojovali proti státní moci. Jejich činnost se soustředila na agitaci v liberálních organizacích za odstranění protikomunistických nařízení a posilování pozic v odborech. V roce 1923 se v Bělehradě uskutečnila Zemská konference KSJ, na níž byla ustavena Nezávislá strana práce Jugoslávie. I ta však byla posléze zakázána a následujícího roku ukončila svou existenci. Snahy organizovat ilegální struktury nebyly příliš úspěšné a narážely na frakční neshody. Zvlášť intenzivně se diskutovalo o citlivé národnostní problematice. Na III. zemské konferenci, která se uskutečnila v lednu 1924 v Bělehradě, byla nakonec přijata Rezoluce o národnostní otázce. Ta navrhovala federativní uspořádání státu republikánského typu s místními samosprávami, čímž byl vyjádřen odklon od prvotních idejí kombinace unitarismu s autonomismem. Požadováno bylo zrušení Vidovdanské ústavy z roku 1921. Definitivně byla zavrhnuta myšlenka o národní jednotě Srbů, Chorvatů a Slovinců a přijat princip, že každý národ v zemi má právo na svůj samostatný suverénní stát a dobrovolné spojení ve federaci. Tuto rezoluci Kominterna rozhodně odmítla na V. kongresu v červenci 1924 a namísto federativního uspořádání žádala odtržení Chorvatska, Slovinska a Makedonie a jejich politickou samostatnost. III. internacionála považovala Jugoslávii za nepřirozený státní útvar a Srbsko za okupanta jugoslávských zemí. V souladu s těmito požadavky se až do roku 1935 jugoslávští komunisté přidržovali direktiv Kominterny o rozbití Jugoslávie.
Mezitím bylo na III. kongresu KSJ v květnu 1926 ve Vídni dosaženo zdánlivého usmíření mezi levou a pravou frakcí. Do čela strany se dostal ke stranické pravici tíhnoucí profesor matematiky Sima Marković. Názorové neshody navzdory tomu pokračovaly i po kongresu. Proti Markovićovi a jeho vlažnému postoji k rozbití Jugoslávie se však postavila Kominterna a extrémní levičáci. Na tajné schůzce chorvatských komunistů 25. 2. 1928 došlo k dalším rozbrojům mezi oběma křídly, načež měla spor vyřešit moskevské vedení internacionály. Nedlouho poté byl na VI. kongresu Kominterny Marković zbaven vedení a vyloučen z KSJ, aniž by o tom věděl. Frakcionářství odsoudil i čtvrtý kongres KSJ 6.–12.11. roku 1928 v Drážďanech. Za politického tajemníka byl vybrán Jovan Mališić (1902–1939) a za organizačního pak Đuro Đaković (1886–1929).
Státní převrat a zavedení královské diktatury 6. ledna 1929 ještě více ztížilo postavení ilegální KSJ, jejího vedení i členstva. Ústřední výbor přestal pracovat jako jednotné vedení ještě v témže roce, politbyro na doporučení Kominterny odešlo do zahraniční na jaře 1930. Výzva strany, aby se lidé se zbraní v ruce postavili proti diktatuře, vyvolala ostrou reakci vlády, která využila všech prostředků při definitivním zničení strany. První smrtelnou obětí se stal Đuro Đaković, šéf humanitární organizace Rudá pomoc Jugoslávie Nikola Hećimović, čtyři tajemníci ÚV a sedm tajemníků Svazu komunistické mládeže Jugoslávie (SKOJ). Do roku 1932 se uskutečnilo osmdesát tři soudních procesů se stovkami komunistů. Mezi odsouzenými na patnáct let nucených prací byli pozdější vyznaní politici Edvard Kardelj, Aleksandar Ranković, Boris Kidrič a mnozí další. V tomto, pro stranu nejtěžším období, členská základna čítala 3500 členů a stejný počet měla komunistická mládež. Celkovou situaci ztížily i časté změny ve vedení strany. V létě 1931 byl po intervenci Kominterny do čela prozatímního vedení dosazen Filip Filipović a Anton Mavrak (1899–1938). Následujícího roku tuto úlohu převzal agilní revolucionář českého původu Milan Gorkić (vl. jménem Josip Cizinski/Josef Čižinský, 1904–1937), který zastával funkci politického tajemníka až do roku 1936.
V roce 1931 král Alexandr vyhlásil novou oktrojovanou ústavu, která počítala s obnovou parlamentního života. Komunistická strana nebyla k vypsaným volbám připuštěna, ale i zavedené občanské strany volby téhož roku bojkotovaly. Nespokojenost s režimem postupem času narůstala, dostatečnou podporu si nezískala ani prokrálovská Jugoslávská radikálně selská demokracie (od 1933 Jugoslávská nacionální strana), a proti státní garnituře stále ostřeji vystupovaly politické subjekty i samo obyvatelstvo. Naopak vládnoucí elita, aby udržela klid, musela zesilovat represe vůči svým odpůrcům. Vyhrocená situace vyústila v úspěšný atentát na Alexandra v Marseille v říjnu 1934.
I přes nelehkou situaci v roce 1932 začala postupná obroda KSJ. Vznikala nová místní a oblastní vedení a rostl i počet členské obce. Z počátečních 300–500 členů roku 1932 členstvo narostlo na 2828 o dva roky později. Na přelomu let 1933 a 1934 Kominterna opětovně přidělila vedení KSJ jméno ústřední výbor, přestože stále sídlilo v zahraničí (ve Vídni, a poté v Brně), a obnovila pravidelné spojení s komunisty v zemi. V srpnu 1934 byl po návratu z nucených prací do politbyra za nevyjasněných okolností kooptován Josip Broz, nepříliš známý stranický aktivista. V roce 1933 bylo zvoleno i prozatímní vedení SKOJ s asi 950 členy.
Konsolidace strany pokračovala i na IV. zemské konferenci v Lublani 24.–25. 12. 1934. Účastnilo se jí osm delegátů z několika regionů a tři představitelé ÚV SKJ, kteří do země přicestovali tajně. Vedle odsouzení vlastní nejednotnosti se komunisté zasazovali za společný boj proti fašismu. Stále aktuální byl vznik nezávislých jugoslávských států, ale již bez zmínky o balkánské federaci socialistických republik. Za tímto účelem bylo rozhodnuto založit komunistické strany Chorvatska a Slovinska a později i Makedonie. Jistá nedůslednost byla patrná v momentě, že podobné strany neměly vzniknout pro Srbsko, Černou Horu a Bosnu a Hercegovinu, jež částečně spadala pod KS Chorvatska. Na konferenci byl také vybrán dvanáctičlenný ústřední výbor a devět jeho kandidátů. Do politbyra byli vybráni Milan Gorkić (politický tajemník), Blagoje Parović (1903–1937), Josip Broz (1892–1980), Kamilo Horvatin (1896–1938) a Adolf Muk (1893–1943). Touto konferencí byla dokončena reorganizace strany po tvrdé represi na přelomu 20. a 30. let.
Na mezinárodní scéně přitom docházelo k výraznému obratu. Vzestupu Německa a Itálie se Sovětský svaz se snažil bránit politikou kolektivní bezpečnosti. SSSR v roce 1934 vstoupil do Společnosti národů a zahájil tak cestu z mezinárodní izolace. Tato převratná změna měla dopad i na celosvětové komunistické hnutí. Na VII. kongresu Kominterny 25. 7.–21. 8. v Moskvě byla přijata rozhodnutí, jež fašismus označila za největšího nepřítele pracujících. Při boji s ním mělo dojít ke vzniku širokých antifašistických lidových front.
Nové volby v Jugoslávii na počátku roku 1935 ukázaly, že i přes vítězství monarchistické Jugoslávské nacionální strany, nové vzniklá Sdružená opozice upevnila své postavení. Komunisté nebyli k volbám připuštěni a podpořili kandidáty opozice. Souběžně s tím přibývaly projevy občanské neposlušnosti, stávky a demonstrace. Již koncem června byla jako vstřícný krok režimu obměněna vláda, do jejíhož čela se dostal konzervativec Milan Stojadinović. Na vládní úrovni vznikla široká koalice pod označením Jugoslávské radikální společenství (JRZ, která spojila dříve zakázané partaje Národní radikální strana, Slovinská lidové strana a Jugoslávská muslimská organizace). Hlavní opoziční subjekty však do nové vlády nevstoupily a pokračovaly v opoziční činnosti.
KSJ se v souladu s doporučeními zabývala změnou kurzu a ústřední výbor koncem března 1935 pozměnil rezoluci ze IV. zemské konference. Korekce se týkaly vyhroceného vztahu k sociální demokracii a proklamování širší politické spolupráce na bázi antifašismu. Diskuze o antifašismu probíhaly na zasedání ústředního výboru ve Splitu 9.–10. 6. 1935 v rámci příprav na VII. kongres Kominterny. Člen Politbyra Blagoje Parović ve svém referátu nastínil politiku lidové fronty, jež by spojila všechny antifašistické síly v Jugoslávii. Stále však byla očekávána krize kapitalistického systému, který se dosud potýkal s dopady hospodářské krize, a neodvratnost socialistické revoluce. Paralelně s novou taktikou lidové fronty docházelo ke změnám pohledu na národnostní politiku. Stále bylo uznáváno právo národa na sebeurčení, ale rozbití Jugoslávie bylo bráno s větším odstupem.
Pod dojmem splitského zasedání byly ještě v červenci zahájeny práce na vytvoření legální Jednotné strany práce. Již v září se uskutečnila přípravná konference. Program lidové fronty byl mezitím komunisty prezentován na masovém shromáždění opozice v Kragujevci 25. 8. 1935. Stále zakázané, ale oproti komunistům masové, Demokratická a Agrární strana však neměly o spolupráci zájem. Komunisté se proto rozhodli o hledání podpory u voličstva a mezi členstvem těchto stran, a nikoli u jejich vedení. Na tomto postoji nic nezměnil ani VII. kongres Komunistické internacionály, jehož se zúčastnili Milan Gorkić a dosud stále málo významný Josip Broz. Cílem stále bylo svrhnout stávající režim, zrušit represivní zákony a domoci se svobodných voleb. Konečné řešení národnostní otázky měla přinést až socialistická revoluce. Mimo jiné se deklarovalo, že tato problematika nemůže být řešena hledáním podpory u velmocí a v nové válce. Žádala se změna samosprávního uspořádání, kdy by zanikly uměle vytvořené bánoviny a zpět by se vrátily historické hranice mezi jednotlivými zeměmi.
Politika lidové fronty přinesla nepříliš výrazný a krátce trvající úspěch ve Slovinsku, kde došlo ke spolupráci komunistů s levicovými skupinami. Po obecních volbách v říjnu 1936 se ale koalice s názvem Slovinská lidová fronta rozpadla. V Chorvatsku byla spolupráce s nejsilnější Chorvatskou selskou stranou (HSS) odmítnuta s odůvodněním, že je idea lidové fronty již realizována v rámci chorvatského národního hnutí pod vedením tohoto uskupení. Komunisté pak vznikl další nepřítel, když HSS roku 1935 obnovila činnost vlastních odborů, Chorvatského svazu práce, jež měl konkurovat jednotným odborům s komunistickým vlivem. Aktivnější styky byly zahájeny se Samostatnou demokratickou stranou v některých oblastech Chorvatska a Bosny a Hercegoviny. Ve Vojvodině se zdařila spolupráce s sociálnědemokratickou levicí a v Černé Hoře vznikaly odbory Fronty lidové svobody. V Makedonii komunisté vycházeli vstříc autonomistickým tendencím a vedli vcelku populární Makedonské národní hnutí (MANAPO). Politika lidové fronty se odrazila i v činnosti SKOJ, jenž přibíral pod svá křídla další mládežnické organizace. Idea fronty se těšila mimořádné podpoře na univerzitách, zvláště té v Bělehradě. Studenti se přidávali ke stávkám a protivládním demonstracím, za což byli mnozí tvrdě potrestáni.
Ke zlepšení činnosti strany v zemi ÚV rozhodl v polovině roku 1935 o založení Zemského byra pro přímé vedení strany. Byro sídlilo v Záhřebu a jeho předsedou se stal Đorđe Mitrović (1903–1937). Po půl roce činnosti bylo členové byra zatčení a tento orgán tak zanikl. I přes mírné zlepšení nebyla situace ve straně nijak snadná. Ve Slovinsku měla KSJ 480 členů, v Chorvatsku a Slavonii 650, v Dalmácii 530, v Srbsku 900, v Černé Hoře, Sandžaku a Kosovu 610 (z toho bylo 430 rolníků), v Makedonii 250 a v Bosně a Hercegovině pouhých 140–150. Celkem asi 4500 členů, a to doma i v zahraničí.
V souvislosti s volbami na počátku 1935 opětovně zesílily represe vůči komunistům. V půli roku skoro ustaly, jelikož Stojadinovićova vláda v těžkém období nestability vyčkávala, ale po upevnění svého postavení se pustila do boje s politickými oponenty v ještě větší intenzitě než kdy dříve. První na řadě byla KSJ, která se dostala pod nejsilnější tlak od roku 1921. Vlna zatýkání začala v Sisku a pokračovala v Záhřebu a Bělehradě, až se následně rozšířila do celé země. Do jara 1936 byla pozatýkána asi tisícovka členů strany a SKOJ. Ustavující sjezd pobočky strany v Chorvatsku, plánovaný na listopad 1935, byl odložen. Do podzimu se počet postižených komunistů a jejich sympatizantů vyhoupl na dvojnásobek a před soudem stanulo asi 800 z nich. Zatčeni byli skoro všichni členové Zemského byra ÚV KSJ, oblastních výborů a další významní politici. Po Záhřebu a Bělehradě, kde bylo zbaveno svobody okolo 240 komunistů, v prosinci 1935 a lednu 1936 následovala Lublaň, a po ní další místa ve Slovinsku. V Dalmácii bylo ve stejné době uvězněno okolo 200 lidí a v Bosně a Hercegovině asi 100. V únoru následovala Makedonie se 70 zatčenými a v únoru a březnu Černá Hora se skoro 300. Během roku 1936 zatkla několik členů a kandidátů ústředního výboru strany také vídeňská policie. V Bosně a Hercegovině byla provedena razie v říjnu v Banja Luce, při níž bylo zatčena většina místních komunistů, a ve Vojvodině postihlo listopadové zatýkání 122 komunistů.
Na rozsáhlé razie vedení KSJ nebylo připraveno a v nastalém zmatku vzniklo několik soupeřících skupin. Na svém zasedání 9. 5. 1936 komunisté v ústředním výboru upozadili vznik lidové fronty a Stojadinovićův režim označili za blízký fašismu. Sporům se nevyhnuly ani personální otázky. Z politbyra byl již v únoru vyloučen za přestupek proti konspiraci Blagoje Parović a další členové byli zatčeni v Praze (organizační tajemník Lovre Kuhar, 1893–1950, a Ivan Krndelj, 1888–1941). Zatýkání ve Vídni, jehož obětí v červnu 1936 byli členové a kandidáti ústředního výboru Karlo Hudomalj, Ivan Marić, Boris Kidrič, Srđe Pric a Dragutin Marušić, ještě více destabilizovalo vedení strany a posílilo nedůvěru v členské základně.
V reakci na dubnovou schůzi ÚV KSJ se v Moskvě v srpnu 1936 uskutečnilo zasedání Výkonného výboru Kominterny, které se zabývalo činností strany v Jugoslávii. Poradě vedle členů Sekretariátu výboru byli přítomni členové ÚV KSJ Milan Gorkić, Josip Broz a Ivan Gržetić a další členové strany pobývající v té době v sovětské metropoli. Mezi nimi byl Blagoje Parović, Rade Vujović, Filip Filipović, Božidar Maslarić, Simo Miljuš, Vilim Horvaj, Dragutin Gustinić a Edvard Kardelj. Na jednání byla kritizována činnost ÚV KSJ a zvláště jeho závěry na dubnovém zasedání, a to s odůvodněním, že se rozcházejí s politikou VII. kongresu Kominterny. Generální tajemník Kominterny Georgi Dimitrov zdůraznil, že v Jugoslávii existují podmínky pro vytvoření lidové fronty s opozičními občanskými stranami a že ÚV KSJ místo toho stranu orientoval výhradně na boj za vytvoření lidové fronty „zdola“. Zhodnoceno bylo, že Jugoslávie byla zavlečena do sféry Hitlerových zájmů, a KSJ proto musí posílit svůj boj proti vládě Milana Stojadinoviće. V oblasti národnostní otázky bylo uvedeno, že se strana musí ještě rozhodněji vyjádřit proti rozdělení země a za rovnoprávnost jejich národů, za demokratickou federativní republiku Jugoslávii. Jmenováno bylo také nové vedení KSJ, do jehož čela se kompromisním řešením vyšvihli Milan Gorkić a Josip Broz. První z nich se zasazoval o pokračování činnosti ÚV v zahraničí a druhý jmenovaný žádal návrat vedení do země. Nakonec bylo rozhodnuto, že Milan Gorkić zůstane v zahraničí (v Paříži) jako spojka s Kominternou a Josip Broz se vrátí do země, aby vytvořil podmínky pro formování nového ústředního orgánu. Toto zasedání mělo pro další chod strany zásadní význam. Počátkem listopadu 1936 bylo vybráno nové vedení KSJ. Vedle Gorkiće a Broze do ÚV KSJ vstoupili Rodoljub Čolaković a Sreten Žujović a člen Oblastního výboru KSJ pro Slovinsko Franc Leskošek. Milanu Gorkićovi, jenž se stal generálním tajemník, byly dány četné pravomoci ve vztahu ke kolektivnímu vedení strany, mimo jiné i právo veta na jeho rozhodnutí.
Nové vedení KSJ v duchu závěrů moskevského zasedání připravilo rezoluci a prohlášení, které byly počátkem roku 1937 poslány do země. V obou dokumentech byly zapracovány postoje z „Dopisu pro Srbsko“, které do země poslal Josip Broz 2. 11. 1936. V nich byl vysvětlen národnostní program pro Jugoslávii. Ten opakoval schválený postoj, že národy Jugoslávie mají být svobodné, ale v současných státních hranicích a na principu federace. Dávalo se za pravdu demokraticko-agrární opozici ohledně úlohy parlamentu, resp. vytvoření zemských parlamentů, které by rozhodly o národní budoucnosti. Právo na národní samostatnost měli mít vedle Srbů, Chorvatů a Slovinců také Makedonci a Černohorci a obyvatelé Bosny a Hercegoviny a Vojvodiny.
V téže době na celosvětové komunistické hnutí silně zapůsobilo dění ve Španělsku, kde po nezdařeném vojenském převratu vypukla občanská válka. Již v roce 1936 byl Tito při svém návratu do vlasti pověřen úkolem organizovat nábor dobrovolníků pro Španělsko. Snaha nalodit 500 dobrovolníků v Černé Hoře v březnu 1937 skončila katastrofálně, jelikož byli všichni ještě před naloděním zatčeni a odsouzeni k těžkému žaláři. Pronajatou loď La Corse zabavila jugoslávská vláda. Další pokusy o přepravu interbrigadistů po moři se již neuskutečnily. KSJ nicméně organizovala i jiné akce solidarity. Jugoslávská vláda, která vyhlásila v konfliktu neutralitu, přitom všemožně bránila vysílání dobrovolníků a lidé odcházející do Španělska byli zatýkání, a ti, jež vstoupili do Španělské republikánské armády, byli zbavováni občanství. I přes všechny překážky na Pyrenejský poloostrov odešlo několik set jugoslávských dobrovolníků. Jako krytí jim posloužila mimo jiné mezinárodní výstava v Paříži roku 1937. Mezi tehdejšími návštěvníky byl i Tito, který si ve městě na Seině otevřel kancelář. O přímé účasti Tita ve válce se dodnes vedou spory. Žádný přímý důkaz přitom nebyl nikdy předložen. Do bojujícího Španělska se mu však podařilo dopravit 1192 Jugoslávců, mezi nimiž bylo nemálo exulantů žijících v zahraničí a jen 330 přibylo ze samotné Jugoslávie. Z nich bylo 561 členů strany, zbytek tvořili sociální demokraté a přesvědčení antifašisté. Ztráty jugoslávských interbrigadistů byly poměrně vysoké, 671 zahynulo a dalších 300 zraněno. Mezi bojovníky byl značný počet tehdejších či budoucích významných komunistů, mezi nimi Blagoje Parović (padl v boji), Ivan Gošnjak, Veljko Vlahović, Peko Dapčević a Ivan Krajačić.
Proti nástupu fašismu se komunisté zapojovali také na domácí půdě formou demonstrací a šířením letáků. V průběhu roku 1937 bylo organizováno několik demonstrací; u příležitosti státní návštěvy italského ministra zahraničí Galeazza Ciana a německého ministra zahraničí Konstantina von Neuratha, a antifašistických shromáždění při státní návštěvě Edvarda Beneše a francouzského ministra zahraničí z lidové fronty Yvona Delbose. KSJ se na podzim 1937 vyslovila proti ratifikaci konkordátu s Vatikánem, jež následně pro odpor pravoslavné církve vzbudil skandál a rozhořčení nekatolické veřejnosti. Komunisté ostře vystoupili proti anschlussu Rakouska. Rozhořčení na postojem lavírující vlády se vyslovili i vysokoškolští studenti. V létě KSJ odsoudila defenzivní politiku Spojeného království a Francie a vyzvala k obraně nezávislosti Československa. Po celé zemi se v září 1938 uskutečnila řada protestů od Mariboru do Skopje. V srpnu se také pod hlavičkou komunistické strany sešlo shromáždění, jež zabránilo slavnostnímu otevření železniční trati Bileća-Nikšić za účasti premiéra Stojadinoviće. Nesouhlas komunistů s vývojem za hranicemi Jugoslávie se projevil i při okupaci Albánie italskými silami, kdy oblastní výbor v Kosovu spíše symbolicky organizoval zápis dobrovolníků na obranu okupované sousední země.
Aby si komunistická strana podržela vliv, musela udržet jednotné odbory, které byly sdruženy ve Sjednoceném svazu práce. Spor se socialistickou pravicí v roce 1937 vyvrcholil odložením kongresu svazu práce na následující rok. Komunistům se podařilo zachovat jednotný svaz s asi 100 000 členy a pod svým vedením. Vláda pak ve snaze uklidnit dělníky přijala nařízení o minimálních mzdách a zakázala stávky v životně důležitých odvětvích. I přes tyto ústupky dělnických stávek výrazně neubylo.
Po neúspěchu s Jednotnou stranou práce a v období přeskupování politických sil, jež vedlo k vytvoření opozičního Bloku národní shody, ÚV KSJ zahájil iniciativu založit novou legální Stranu pracujících, aby tím umožnil účast komunistů v tomto opozičním táboře. Hlavní přípravný odbor měl sídlo v Záhřebu. Jeho předsedou se stal Božidar Adžija. Posléze vznikly oblastní a místní přípravné odbory. Zveřejněna byla platforma strany, ve které byly obsaženy základní požadavky z dřívější platformy Fronty národní svobody, resp. Jednotné strany práce. V polovině roku 1938 se v Záhřebu uskutečnila ustavující konference, na které byli přítomni delegáti z Makedonie, Srbska, Černé Hory, Dalmácie, Chorvatska a Slovinska.
Navzdory usilovné snaze Strana pracujících nevstoupila do Bloku národní shody. Opětovně se opakoval rok 1935 s Jednotnou stranou práce, s níž opoziční občanské strany odmítly jednat. Z toho důvodu KSJ strana vstoupila do voleb na podzim 1938 prostřednictvím Strany pracujících samostatně (ve Vojvodině, Srbsku, Bosně a Hercegovině a Dalmácii), prostřednictvím Rolnicko-dělnického hnutí (ve Slovinsku) a Dělnicko-rolnické strany (v Černé Hoře). Pouze v Chorvatsku, kde zesilovaly separatismus a nacionální vášně, někteří členové strany podpořili Chorvatskou selskou stranu na kandidátce opozice.
V průběhu času docházelo i ke změnám v samotné KSJ. Po Titově návratu bylo nastoupena cesta k založení komunistických stran Chorvatska a Slovinska. Nejprve se počátkem roku 1937 uskutečnila porada s Oblastním výborem KSJ pro Slovinsko, aby se odstranily spory mezi ÚV KSJ a oblastní organizací, ke kterým došlo pro separatistické tendence části Slovinců. Na žádost Tita ÚV KSJ navrhl, aby se z Moskvy vrátil Edvard Kardelj. Ten se měl podílet na narovnání situace a pomohl by s přípravami na ustavující kongres. Kongres samotný se uskutečnil 17.–18. 4. 1937 v Čebinách. V přijatém manifestu komunisté Slovinska vyjádřili nutnost spolupráce při boji s fašismem a nacismem a při zápasu za demokratické změny – federativní uspořádání, svolání konstituanty a pomoc slovinským menšinám v sousedních zemích. KSS se nezříkala sjednocení všech Slovinců v jednom státě. Zároveň bylo řečeno, že vytvoření strany má vést k posílení strany a od komunistů se očekává rozhodný boj se separatisty a nacionalisty. Na kongresu byl vybrán ÚV KSS s devíti členy a třemi kandidáty, jakož i dva kandidáti do ÚV KSJ. Tajemníkem ÚV byl zvolen Franc Leskošek.
Přípravami na ustavující sjezd KS Chorvatska se zabýval sám Josip Broz. Kongres se uskutečnil 1.–2. 8. 1937 v Anindolu poblíž Somboru. Tito zdůvodnil vznik strany shodou zájmů pracujících a „pravých zájmů chorvatského národa“. Zároveň byl požadován boj proti nacionální malosti a šovinismu. K tomu se očekávala spolupráce Chorvatů s dalšími národy při sesazení vlády a v boji za demokratická práva a svobody. V tomto případě se opakovaly požadavky ze Slovinska s tím, že se upozorňovalo na nenávist šířenou vůči Srbům. Na kongresu byl vybrán ÚV KSCH a jeho tajemníkem se stal Đuro Špoljarić.
Vznik dvou regionálních poboček strany vycházel vstříc vzrůstajícími separatismu zdejších organizací, které tím více či méně reagovaly společenské klima v daných oblastech.
Změny dolehly i na komunistickou organizaci mládeže. Na jaře 1937 byla zřízena Ústřední mládežnická komise při ÚV KSJ s Ivem Ribarem v čele, která dočasně převzala vedení SKOJ. Tato organizace prošla obnovou a rozšiřovala své řady. Komise v polovině následujícího roku přerostla na ÚV SKOJ. Během let 1937–1939 byly zformovány mládežnické komise ve všech koutech země. V polovině roku 1939 měl pak SKOJ okolo 9000 členů.
V létě 1937 postihly KSJ dalekosáhlé změny, které dovedly v otázku samu její existenci jako sekce Kominterny. V polovině roku byl její generální tajemník Ivan Gorkić pozván do Moskvy. Za měsíc byl již ze stranické funkce sesazen a brzy nato zatčen. Během let 1937–1938 bylo uvězněno dalších více než 100 jugoslávských komunistů. Mnozí z nich byli obviněni jako „imperialističtí špioni“ a „trockisti“ a hned nato z valné části zastřeleni nebo se po nich slehla zem. Byli mezi nimi Filip Filipović, Vladimir Ćopić, Sima Marković, Đuro a Stjepan Cvijićové, Kamilo Horvatin, Ivan Gržetić, Kosta Novaković, bratři Vojislav, Radomir a Grgur Vujovićové a další. V polovině srpna 1937, kdy na pozvání členů politbyra ÚV KSJ Rodoljuba Čolakoviće a Sretena Žujoviće přicestoval do Paříže, Josip Broz za dosud nevyjasněných okolností převzal post tajemníka strany a o této změně informoval Výkonný výbor Kominterny. Zároveň vedení internacionály sdělil, že nemůže v nejbližší době odcestovat do Moskvy kvůli reorganizaci politbyra. Byl to velmi obratný krok, jelikož se tím vyhnul reálně hrozícímu nebezpečí v SSSR a mohl se věnovat upevnění svého postavení ve straně. V době vykonávání funkce se však setkal s neočekávanými těžkostmi, neboť kontakty s Kominternou byly stále slabší a straně byla zastavena nezbytná finanční pomoc. Mezi členy KSJ vypukly frakční spory. V důsledku zatčení Milana Gorkiće a rezervovaného vztahu Moskvy k Brozovi a ÚV se Ivan Marić a Labud Kusovac snažili na vlastní pěst spojit s komunisty v Jugoslávii (mj. s vězněným radikálem Petkem Miletićem) a o něco později bylo v Paříži zformováno paralelní centrum moci na čele s Ivanem Marićem. Koncem roku 1937 vedení Kominterny povolalo do Moskvy členy politbyra Rodoljuba Čolakoviće a Sretena Žujoviće. Vedení KS Francie, prostřednictvím které jugoslávská emigrace zasílala pomoc KSJ, Brozovi nadobro zastavilo přísun financí. Narušené vztahy s Kominternou byly znát i u jugoslávských komunistů ve Španělsku. Někteří byli zbavováni vedení a nevyhnuli se dohledu. Změnilo se také postavení představitelů KSJ při ÚV KSUSA A ÚV KS Kanady i v dalších zemích. Reálně hrozilo nebezpečí, že KSJ bude rozpuštěna jako se to stalo v Polsku a Koreji. Broz se v tomto období snažil udržet politickou aktivitu strany v zemi tak, že zůstal ve spojení s Edvardem Kardeljem a Ivanem Ribarem, a scházel se se zbylými členy vedení v Paříži. Vedle Mariće a Kusovce se jednalo o Čolakoviće, Žujoviće, Ivana Krndelje a Lovru Kuhara. Snažil se také získat podporu i mezi prominentními 200 členy strany ve sremskomitrovickém vězení na domácí půdě. Tímto úkolem pověřil Moše Pijade a Andriju Hebranga, jimž se podařilo převzít iniciativu a Brozova hlavního oponenta, bývalého člena politbyra a radikálního levičáka Petka Miletiće a jeho nejbližší, zbavit vlivu.
Broz stále hájil myšlenku přenést vedení strany do Jugoslávie, o čemž informoval Georgie Dimitrova. Sám se vrátil do Jugoslávie v březnu 1938. Začátkem května se zformovalo prozatímní vedení KSJ, v jehož sestavě byli Brozovi oddaní Edvard Kardelj, Franc Leskošek, Miha Marinko, Josip Kraš, Drago Petrović, Andrija Žaja, Milovan Đilas a Aleksandar Ranković. Přestože nové vedení nemělo s ohledem na tehdejší praxi Kominterny a status strany postavení ÚV, jeho zřízení mělo významný dopad. Prozatímní vedení se pustilo do nezbytné reorganizace strany.
Ve snaze vyřešit postavení KSJ Broz udržoval kontakt s Kominternou, načež v srpnu 1938 z vlastní iniciativy, ale se sovětským vstupním vízem, přicestoval do Moskvy. Situace na místě byla horší, než se domníval. V té době ještě probíhaly čistky mezi jugoslávskými komunisty. Úloha Broze na zatčeních a rozsudcích jeho spolustraníků není dosud vyjasněna. Jisté je však, že celá řada zatčení a poprav proběhla již před jeho příchodem a nemohl na ně tedy mít jakýkoli vliv. Broz a několik dalších jugoslávských komunistů bylo pověřeno překladem Stalinových Dějin Všesvazové komunistické strany (bolševiků) do srbochorvatštiny. Mezitím byl Broz několikrát obviněn z trockismu, vždy ale vyvázl bez trestu. Pravděpodobně na to měly vliv dobré styky, proletářský původ, charisma a v neposlední řadě i jeho neintelektuální povaha. Časté kontakty s Georgiem Dimitrovem, Wilhelmem Pieckem (od 1938 generálním tajemníkem Kominterny) a Ivanem Karaivanovem (členem NKVD) mu byli jistě velmi užitečné. Na jeho přežití se odrazily i nepředvídatelné okolnosti na poli mezinárodní politiky. Mezi nimi lze vyzdvihnout vývoj v Československu a sbližování pravicových vlád Polsku a Maďarsku s Hitlerovským Německem. Kromě jiného začali jugoslávští komunisté organizovat dobrovolníky na obranu Československa a manifestací na podporu ohrožené republiky se účastnily tisíce lidí. To vše bylo z větší části připisováno Brozovi.
Nakonec byl 5. ledna 1939 na zasedání Sekretariátu Výkonného výboru Kominterny Brozovi potvrzen mandát řídit prozatímní vedení. Ohledně pověření vést stranu jako generální tajemník KSJ se vedou debaty. Není totiž jasné, jak silné pověření Broz dostal a zda mu bylo dovoleno ustavit regulérní ÚV. Kominterna Broze jako generální tajemníka totiž poprvé oslovila až na podzim roku 1940. Krátce po zasedání Sekretariátu se Tito vrátil do vlasti, kde podle oficiální interpretace KSJ zřídil ústřední výbor, tj. prozatímní vedení přetransformoval na ústřední výbor. Tento akt se udál na schůzi stranického vedení 19.–21. března 1939. Do ÚV bylo zvoleno kromě Broze dalších šest členů, Drago Petrović a Andrija Žaja jako členové prozatímního vedení nebyli znovu vybráni. Na jednání bylo rozhodnuto vyloučit všechny bývalé členy nejužšího vedení strany, kteří byli v SSSR zabiti a nebo se nacházeli v moskevských věznicích. Na následujícím zasedání o deset dní později byl přijat Titův návrh zveřejnit Otevřený dopis členům KSJ, v němž byl vysvětlen postup komunistů v následujícím období. Jednalo se především o výzvu k loajalitě a jednotě uvnitř strany. Do toho se promítala soudobá atmosféra, kdy se začaly šířit informace o stalinských čistkách. Jednoznačně se hovořilo o nutnosti pročistit stranu od všech nepřátelských elementů.
Následně se 9.–10. června uskutečnila porada stranického vedení za účasti 29 stranických činitelů z ústředního výboru i oblastních výborů, vyjma z Makedonie a Dalmácie. Shromáždění se neslo v duchu shody a přítomní byli obeznámeni s vývojem v zemi i zahraničí. Schváleno bylo jmenování nového ÚV i jeho závěry v personálních otázkách.
