Potom ako guatemalský prezident Arbenz vyprovokoval svojou politikou USA, došlo – tak ako to už v Latinskej Amerike chodí – k jeho pádu. V júni 1954 bol za pomoci CIA zrealizovaný štátny prevrat, ktorý viedol Carlos Castillo de Armas. Che sa chcel zúčastniť na obrane režimu, ale Arbenzova nerozhodnosť (váhal rozdať zbrane ľudu) mu v tom zabránila.22
Pár dní po prevrate požiadal Ernesto o azyl na argentínskom veľvyslanectve, pretože dostal od priateľa avízo, že mu hrozí nebezpečenstvo zo strany CIA. Rezident CIA v Guatemale D.A. Phillips dostal v dňoch prevratu na stôl papier so životopisnými informáciami o 25-ročnom argentínskom lekárovi a hoci mu jeho meno nič nehovorilo, založil na neho zväzok, ktorý sa nakoniec stal jedným z najhrubších v dejinách CIA.23

Koncom augusta sa politická situácia v Guatemale upokojila a Che mohol opustiť veľvyslanectvo. Stretol sa s Hildou a dohodli sa, že odídu do Mexika. V polovici septembra prišiel do Ciudad de Mexico, o ktorom svojej tete Beatriz napísal, že „je to svetové hlavné mesto korupcie“.24 Začiatky jeho života v Mexiku neboli ľahké. Nemal peniaze, ani priateľov, ale nakoniec mu pomohol jeden z priateľov jeho otca. Che si kúpil fotoaparát a živil sa fotografovaním amerických turistov v Mexiko City. Tiež pracoval vo všeobecnej nemocnici, ale podobne ako v Guatemale, ako zle platený laborant. Taktiež vedecky publikoval, čo mu dopomohlo, aby získal grant od Všeobecnej nemocnice. Tak, ako aj v iných krajinách podnikal exotické výpravy, napr. výstupy na sopku Popocatépetl.25 V tej dobe narazil v nemocnici na Ňica Lopéza, jedného z kubánskych priateľov, s ktorými sa zoznámil v Guatemale.26 Ten ho zoznámil z Raúlom Castrom. O pár dní prišiel do Mexika aj Raúlov brat Fidel a Raúl pozval Che, aby sa s ním porozprával.27

Život Ernesta Guevaru sa po schôdzke s Castrom zmenil. Čoskoro začal výcvik pre ozbrojený boj na Kube. Spočiatku bol len povrchný, a skladal sa len z pochodov po Mexiku City, veslovania a cvičenia pod dohľadom mexického zápasníka Arsacia Venegasa. Keď sa stal výcvik serióznejším, Fidel ho presunul na ranč Santa Rosa pri meste Chalco, 80 km od hlavného mesta. V tej dobe však Che ešte nebol úplne rozhodnutý pripojiť sa k výprave. Vždy sníval o ceste do Európy a tiež tu bol faktor, že bol cudzinec a mohol byť pre Fidela príťažou.28

24. júna 1956 bola povstalecká skupina zadržaná mexickou políciou. Fidelovi sa podarilo kombináciou svojej politickej geniality a podplácaním dostať von celú skupinu až na Calixta Garciu a Che Guevaru. Che Fidelovi povedal, aby sa kvôli nemu nezdržovali prípravy. Fidel mu na to odpovedal: „Neopustím ťa.“29 Nakoniec v auguste prepustili z väzenia aj Guevaru, pre ktorého to bol jediný kontakt z väznením až do jeho zajatia v Bolívii. Už od apríla 1956 trénovali revolucionári pod vedením generála Alberta Baya, veterána španielskej občianskej vojny. Che v tomto výcviku získal najlepšie hodnotenia zo všetkých aj napriek obrovskému fyzickému vypätiu a nadmorskej výške, ktoré neprospievali jeho astme.

CHE A KUBÁNSKY ZÁZRAK

V noci 25. novembra 1956 vyplávala z mexického prístavu Tuxpan jachta Granma. Jachta s kapacitou 20 miest viezla 82 mužov, potraviny, vodu, šatstvo, dve protitankové delá, 35 pušiek s optickým zameriavaním, 55 pušiek M-1 Garand, 3 samopaly značky Thompson, 40 automatických pištolí a strelivo. Na tejto jachte sa nachádzal aj Argentínec Ernesto Guevara, ako lekár povstaleckej skupiny s hodnosťou poručika.

Plán vylodenia bol skoordinovaný s Hnutím 26. júla, ktoré na ostrove viedol Frank País. Jeho skupina mala zahájiť 30. novembra ľudové povstanie v Santiagu, zatiaľ čo výsadok z Granmy mal operovať v meste Manzanillo v provincii Oriente. Namiesto toho loď pristála až 2. decembra na pláži Los Coloradas, plnej mangrovových bažín. Povstalecká armáda sa musela týmito bažinami predierať, pričom na člne ostala väčšina zásob, pretože ich postavenie už bolo objavené armádou.
5. decembra 1956 došlo k prvej zrážke revolúcie. Povstalci sa utáborili na trstinovej plantáži Alergiá de Pío. Armáda ich objavila a začala po nich páliť z krytých postavení, a keď sa rozutekali po trstinovom poli, tak ho zapálila. Bol to prvý kontakt Che Guevaru so smrťou.

Celú túto situáciu si zapísal do svojho denníka: „Okolo 4. hodiny popoludní zaznel náhle a bez akejkoľvek výstrahy prvý výstrel. Po ňom sa nad našimi hlavami, ktoré si dosiaľ nezvykli na tento mužný šport, rozoznela olovená symfónia. Jeden súdruh padol a ja sám som mal nepríjemný dojem, že práve dostávam krst ohňom a krvou. Vyviazli sme odtiaľto buď jednotlivo, alebo v skupinkách. Už som nemohol ísť a tak do mňa comandante Almeida poriadne strčil a prikázal mi, aby som pokračoval v ceste. Len vďaka tomu som tam neostal. Zdalo sa mi, že preživam posledné okamihy svojho života… Náhle sa ozval výkrik: Trstinové pole horí!“30 Che musel pokračovať ďalej aj napriek zraneniu krčného svalu, ktoré mu spôsobila guľka.

Bitka sa skončila neorganizovaným útekom povstalcov. Väčšina povstalcov však padla v trstinovom poli, alebo boli zajatí a na mieste popravení armádou. Che pochodoval smerom na Sierru Maestru, najvyššie kubánske pohorie, spolu s Ramirom Valdézom, Camilom Cienfuegosom a Juanom Almeidom. Títo všetci zohrali na Kube kľúčové úlohy v nasledujúcich mesiacoch a rokoch. O tomto pochode si urobil Che záznam do denníka: „Na čele s Almeidom sme zadržiavali nápor a ustupovali, kým nás, hoci sme už boli blízko miesta stretnutia, nezastavila príšerná tma… Prišli sme o všetok výstroj okrem zbraní a dvoch vlajok… Šli sme deväť dní, neznesiteľne sme hladovali, museli sme žuvať trávu a surovú kukuricu… Chýry, ktoré prichádzali boli všelijaké: aj zlé, aj oduševňujúce. K správam o zločinoch, ktoré sa diali vôkol nás, pribudla jedna zvlášť povzbudzujúca: Fidel žije.“31

V Sierre Maestre sa podarilo zvyšným dvanástim mužom sformovať za pomoci skupiny Celie Sanchezovej. Už v polovici januára sa im podarilo uskutočniť úspešný útok na vojenské postavenie v dedine La Plata. To ohlásilo Kube, že povstalci sú dosiaľ nažive a dokonca aj schopní viesť vojnu. Počas útoku došlo aj k prvej poprave. Tým popraveným bol armádny informátor Chicho Osorio.
Počas počiatočných mesiacov pobytu na Sierre sa Che stretol s viacerými mestskými vodcami Hnutia. Medzi inými aj s Frankom Paísom, po ktorom poslal list svojej rodine do Argentíny. V tomto období sa taktiež ujala jeho prezývka „che“, čo v argentínskej hovorovej reči znamená zvolanie „hej“. Toto slovo používal na konci takmer každej vety. Vykonal aj svoju prvú popravu v partizánskych radoch. Tým popraveným bol Eutimio Guerra a Che ho zastrelil sám.
Vyhliadky partizánov sa zlepšili začiatkom marca 1957, keď Fidel poskytol interview Herbertovi Metthewsovi z New York Times a ukázal tak celému svetu, že je nažive.

Hlavným Guevarovým prínosom pre ich povstaleckú armádu bol jeho bojový duch. Ako spomína Pombo, ktorý ho neskôr sprevádzal v Kongu aj v Bolívii, „bol mužom, ktorý v boji rád viedol, dával príklad a nikdy nepovedal bež a bojuj, ale skôr nasleduj ma do boja“.32 Vďaka svojej statočnosti bol Che 21. júla 1957 povýšený na majora (comandante). On to okomentoval takto: „Dávka ješitnosti, ktorú máme v sebe všetci spôsobila, že som sa cítil ako najpyšnejší člověk pod slnkom.“33
Koncom roka 1957 už v Sierre Maestre operovali dve povstalecké kolóny34 : Fidelova o sile 120 mužov a kolóna vedená Che Guevarom, 40-členná, na oklamanie nepriateľa označená ako štvrtá. Che sa so svojou kolónou pokúsil o založenie prvého stacionárneho tábora tejto vojny. Nechal postaviť pec na chlieb, ošetrovňu, dielňu na topánky. Začal vydávať časopis El Cubano Libre a potom zriadil Radio Rebelde.35 O niekoľko týždňov zaútočila armáda a Che bol nútený ustúpiť hlbšie do hôr. Základňu nebolo možné v tej dobe udržať.36 Na druhej strane však priniesol do vojny zmenu v rámci bojových akcií. Prešiel od stratégie „uhryzni a uteč“ k pozičnej vojne, keď museli partizáni brániť nimi vydobyté územie.

Na jar 1958 uskutočnil Batista svoju veľkú ofenzívu. Mala trvať viac jako dva mesiace a zúčastnilo sa jej viac ako 10 000 vojakov. Na druhej strane mali partizáni iba 321 mužov. Ofenzíva bola nakoniec fiaskom. Armáda stratila viac ako 1000 mužov, navyše ich 400 padlo do zajatia a povstalci ukoristili 500 pušiek a dva ľahké tanky. Batistov pád bol už iba otázkou času.
V auguste 1958 už Fidel vedel, že vojnu vyhral. Podarilo sa mu otvoriť druhý front v Sierre de Cristal pod velením jeho brata a teraz musel uchopiť do svojich rúk aj politickú moc v krajine. Rozhodol sa, že rozdelí ostrov na dve časti. Do stredu ostrova preto vyslal dve kolóny: jednu pod vedením Che Guevaru o sile 150 mužov a druhú pod vedením Camila Cienfuegosa s 90 bojovníkmi.37 Oba útvary sa mali v provincii Las Villas spojiť s ostatnými odbojovými skupinami a dosiahnuť spoločnú dohodu.38 Che vyrazil zo Sierry Maestry 31. augusta 1958. Prechod nepriaznivým terénom39 trval 46 dní a bol plný hladu a nebezpečenstiev zo strany armády. Guevara začal operovať na juhu provincie, zatiaľ čo Cienfuegos na jej severe.40 V priebehu novembra a decembra sa im podarilo prerušiť komunikácie cez stred ostrova a zablokovať dopravu. Vojenské víťazstvá nasledovali v rýchlom slede.