その後、アルマス新政権によってゲバラの暗殺指令が出されたため、妻のガデアとともに、失意と怒りを抱いてメキシコに移る。1955年7月、この地に亡命中の反体制派キューバ人のリーダーである、フィデル・カストロと出会う。7月26日運動を率いてキューバのフルヘンシオ・バティスタ独裁政権打倒を目指すカストロに共感したゲバラは、このとき、一夜にして反バティスタ武装ゲリラ闘争への参加を決意したとされている。こうしてスペイン内戦で共和派の生き残りとなったアルベルト・バーヨ中佐による本格的な軍事訓練を受けて、キューバ上陸への準備が進んでいった。
革命家ゲバララバに乗って　1958年11月、ラスビラスにて

妻と娘のイルディーダをメキシコに残し、単身キューバへ向かう。1956年11月25日、フィデル・カストロをリーダーとした反乱軍総勢82名はプレジャーボート「グランマ号」に乗り込んだ。しかしこの「グランマ号」は7人乗りで、その10倍以上も詰め込んだ収容過多によって衛生環境などが劣悪となったことに加え、目立たぬよう、嵐の中出航したことなどもあり、7日後にキューバに上陸した時にはすでに体力を消耗し、それに伴い士気も下がっていた。さらに反乱軍の上陸をカストロが事前に発表し、計画の内容もキューバ政府に漏洩していたため、反乱軍は上陸直後に政府軍の襲撃を受けて壊滅状態となった。結局生きて上陸できたのは82人中、ゲバラ、フィデル・カストロ、ラウル・カストロ、カミーロ・シエンフエゴスなどを含む12人のみだった[注釈 1]。オルトドクソ急進行動の指導者で部隊の副官格のマヌエル・マルケスやバヤモ兵営襲撃の生き残りニコ・ロペス（ゲバラとカストロの仲立ちをした）ら多くの人間が拷問のすえ虐殺された。

上陸後、反乱軍はシエラ・マエストラ山脈に潜伏し、山中の村などを転々としながら軍の立て直しを図った。その後キューバ国内の反政府勢力との合流に成功し、反乱軍は徐々に増強されていった。当初、ゲバラの部隊での役割は軍医であったが、革命軍の政治放送をするラジオ局（ラジオ・レベルデ）を設立するなど、政府軍との戦闘の中でその忍耐強さと誠実さ、状況を分析する冷静な判断力、人の気持ちをつかむ才を遺憾なく発揮し、次第に反乱軍のリーダーのひとりとして認められるようになっていった。上陸から1年後の兵員増加に伴う部隊の再編成に際して、カミーロやラウルらを差し置き、カストロから第2軍（名前の上でだけは第4軍）のコマンダンテ（司令官。司令官の下に分隊がある。分隊指揮者は「隊長」）に任命され、指揮権と少佐の階級を与えられ、名実ともにカストロに次ぐ反乱軍ナンバー2となった。
革命成就1959年1月2日、革命成就直後に

1958年12月29日にはこの第2軍300人を率いて政府軍6000人が迎え撃つキューバ第2の都市サンタ・クララに突入する。そこで、政府軍の武器と兵士を乗せた装甲列車を転覆させ政府軍を混乱させる。反乱軍を支援する多数の市民の加勢もあり、激戦の末にこれを制圧し、首都ハバナへの道筋を開いた。

1959年1月1日午前2時10分に、フルヘンシオ・バティスタがドミニカ共和国へ亡命し、1月8日カストロがハバナに入城、「キューバ革命」が達成された。闘争中の功績と献身的な働きによりキューバの市民権を与えられた。

革命成立6ヵ月後の1959年6月、ゲバラはカストロの特使、6人の親善使節団の団長としてアラブ連合（エジプト、シリア）やユーゴスラビア、インド、ビルマ、インドネシア、アフリカガーナなど11ヶ国歴訪の旅に出た[1][2][3]。当時欧米・ソ連に対して「第三世界」と呼ばれた国々にキューバ革命の真実を伝えるとともに、親善友好を促進しようという狙いであった[1]。出発前は日本はスケジュールに組まれていなかったが、7月4日、神田襄太郎駐キューバ大使に日本に行く旨の正式通告があった[1]。カストロが日本びいきであったとされ[1]、ゲバラも日本人の精神力や勤勉さ、日本の心を高く評価していたことが「第三世界」ではない日本を訪問国に選んだ動機とされる[4]。日本訪問は、それ以外に特産の砂糖の輸出を増やし、その資金で農業や繊維などの軽工業機械、漁船、武器の購入に充てたいという経済使節の役目も兼ねていた[1]。