Huber Matos nació el 26 de noviembre de 1918 en Yara, provincia de Oriente (Cuba), en el seno de una familia humilde. Se graduó en la Escuela Normal para Maestros de Santiago de Cuba y se doctoró en Pedagogía en la Universidad de La Habana en 1944. Su profesión de maestro rural le expuso a las duras condiciones en las que vivía el campesinado cubano en aquel entonces; eso le llevó a comprometerse políticamente desde temprana edad, y ya de modo más activo tras el golpe de Fulgencio Batista en 1952.

Cuatro años después se unió a la guerrilla (concretamente al movimiento "26 de julio" de Fidel Castro, que surgió a raíz del asalto a la Moncada el 26 de julio de 1953) y se convirtió en uno de sus líderes más carismáticos. A modo de ejemplo, estuvo a cargo de la toma de la Ciudad de Santiago, la segunda en importancia del país isleño.

Ocupó puestos de responsabilidad al lado de Fidel Castro hasta que éste se hizo del poder en enero de 1959; en los meses que siguieron, se contó entre los más importantes dirigentes del país y tuvo a su cargo la provincia de Camagüey (principal región ganadera de la isla), hasta que sus divergencias ideológicas con la política de Castro precipitaron su detención; tras un juicio sumario, fue enviado por 20 años a la cárcel.