Keď povstalecká armáda odrazila ofenzívu vládnych vojsk a fronty sa stabilizovali, obdržal Che Guevara rozkaz k presunu svojich jednotiek do strednej provincie Las Villas.

Partizánske jednotky sa rozrastali a silneli stálym prílivom ďalších dobrovoľníkov a získavaním nových zbraní. Partizánska vojna sa dostávala do záverečnej fázy. V rozkaze vrchného velenia povstaleckých vojsk bola určená ako hlavná úloha partizánov v oblasti Las Villas systematicky narušovať dopravu a spoje medzi V a Z ostrova. Che Guevara, ktorý bol určený ako veliteľ pochodu, bol súčastne poverený, aby sa spojil so všetkými politickými ozbrojenými skupinami, operujúcimi v oblasti strednej provincie Las Villas.

Bol vybavený širokou právomocou ustanoviť vojenskú vládu nad touto oblasťou. 600 km dlhý „veľký pochod“ začal 31. augusta 1958 a trval do 16. októbra 1958. Neustále boje s nepriateľom na zemi aj vo vzduchu, hlad, smäd, horko, močiare a hory, choroby aj zranenia, to všetko sprevádzalo partizánov na každom kroku. Počas novembra a decembra prerušili povstalecké vojská všetky cesty a spoje v Las Villas. Na hlavnej diaľnici vedúcej cez celú Kubu, bol zničený most cez rieku Tuynicay. Hlavná trať bola prerušená na niekoľkých miestach. Ostrov bol rozdelený na dve časti.

Vládne vojská, izolované v provincii Oriente, mohli byť podporované a zásobované iba zo vzduchu. Tu prebiehali najúpornejšie boje a postavenie vládnych vojakov sa stávalo každým dňom beznádejnejším. 16.decembra začali povstalci systematicky rušiť spoje a cesty. Predné jednotky batistovej armády boli izolované aj od svojich základní. Údery povstaleckého vojska v horách i odpor organizovaný Ľudovou socialistickou stranou Kuby v mestách a v najširšej spolupráci s Hnutím 26. Júla a odbormi ochromili moc vlády a režimu tyranie, ktorý sa koncom decembra 1958 zrútil.

Keď povstalci obsadili mesto Santa Clara východne od Havany, Batista opsitl krajinu a odišiel do exilu v Portugalsku a Španielsku. Castrove jednotky vstúpili do Havany 1. januára 1959.

Fidel Castro sa stal premiérom Kuby vo februári 1959. V roku 2006 je najdlshšie vládnucou hlavou vlády na svete. Bol konštitučný liberálny nacionalista a napriek jeho radikálnosti bolo jeho víťazstvo vítané na Kube aj v USA. V roku 1959 Castrova vláda zahájila pozemkovú reformu a boj proti korupcii a znárodnenie zdrojov vrátane zrušenia hazardu a vypovedanie amerických mafiánov. Mnohým ostal zakrytý vplyv Ernesta “Che” Guevarau, argentínskeho marxistu a jedného z najbližších Castrových poradcov. Guevara vytvoril alianciu s Castrovým ambicióznym bratom Raulom aby presvedčili Fidela Castra k spojenectvu s komunistami a teda so Sovietskym Zväzom.

Guevara zohral kľúčovú rolu aj pri presviedčaní vodcu kubánskych komunistov Blasa Roca Caldería aby zanechal nepriateľstvo s Castrom. Roca informoval sovietske vedenie o možnostiach spolupráce. Sovieti boli zaujatí šancou presadiť politický vplyv v Amerike a prisľúbili neobmedzenú pomoc, ak sa Castro pridá ku komunistom.

Názory na revolúciu v USA sa zatiaľ rýchlo menili. Eisenhowerova administratíva ešte pád Batistu vítala, znárodnenie amerických spoločností a prenasledovanie konzervatívcov s konexiami v USA viedli k vzniku mocnej lobby. Castro sám nebol známy ako komunista, pod vplyvom Guevaru sa však s nimi začal zbližovať a nepriateľstvo USA ho v tom utvrdilo, takže liberálne a antikomunisticé elementy hľadali útočište v Miami.

V roku 1960 boli podpísané prvé dohody o pomoci a spolupráci so ZSSR. V kontexte studenej vojny bolo vytvorenie zákldne sovietskeho vplyvu v Amerike pre USA neprijatelné, preto začali pripravovať plány na Castrove zosadenie. V roku 1960 zaviedli obchodné embargo, ktoré však v skutočnosti dostalo Castra celkom do sovietskych rúk. Po nevydarenej invázii exilantov v Zátoke Svíň v apríli 1961 prehlásil Castro Kubu za socialistickú republiku.