Hijo de Enrique Deheza y de María de la Trinidad Millán y de la Hoz. Dio sus primeros pasos en la carrera de las Armas incorporándose a las fuerzas patriotas que marchaban en campaña hacia el Alto Perú bajo las órdenes del general Antonio González Balcarce. En 1813, siendo teniente, marchó hacia Chile con la División auxiliar bajo el liderazgo de los generales Juan Gregorio Las Heras y Balcarce. Luchó, en 1814, en los combates de Cucha-Cucha y Membrillar.

Se enroló en el Ejército Libertador de los Andes bajo el mando del general José de San Martín en el Regimiento 11 de Infantería. Ostentaba el grado de capitán cuando combatió en las acciones de Plumerillo, Guardia Vieja, Chacabuco, Concepción, Gavilán, Talcahuano, Cancha Rayada y Maipú. En 1820 integró la misión emancipadora del Perú comandando el Regimiento 11 de Infantería. Participó de la campaña de la Sierra bajo las órdenes del general Arenales y por su destacada labor mereció el ascenso al grado de teniente coronel. Intervino en el sitio del Callao, luchó en las batallas de Torata y Moquegua, realizó la campaña de Arica y la de Lima y combatió en Junín y Ayacucho, sellando en forma definitiva la emancipación del Perú. En 1825 fue nombrado, por el general Simón Bolívar, jefe del Estado Mayor del Ejército Libertador. Se hizo cargo, hasta 1826, en forma interina, de la prefectura del departamento de Guanuco. [...]