A los 17 años comienza su vida castrense, ingresando en la Academia General Militar de Zaragoza. De ella salió en 1933, a los 21 años, siendo el primero de su promoción, graduado como Teniente de Artillería. Estuvo destinado en Segovia y Carabanchel, hasta que en 1936 estalla la guerra civil.
Gutierrez Mellado, perteneció a uno de los tantos regimientos sublevados el 18 de julio. La zona en la que se encontraba fue rodeada, por lo que fue detenido y encarcelado en la cárcel de San Antón. En 1937 fue absuelto en un juicio, y consiguió refugiarse en la embajada de Panamá, con muchos otros nacionales. Consiguió cruzar las líneas y volver a zona nacional. Participó en el Servicio de Inteligencia Militar, y fue un infiltrado quintacolumnista dentro de las líneas enemigas. Usó una identidad falsa, Teodosio Paredes, con la que recababa información en Madrid y ayudaba a nacionales a cruzar al territorio de su bando.
Finalizada la guerra, siguió su larga carrera en el ejército, donde vivió sucesivos ascensos en el rango: así fue ascendido a Capitán en 1938, Comandante en 1942, Teniente Coronel en 1957, Coronel en 1965 y General de Brigada en 1970, siendo destinado al Alto Estado Mayor de la Defensa. En 1973 es ascendido a General de División, y es destinado como jefe de la Capitanía General y la Gobernación de Ceuta. Tras la muerte de Franco, sigue subiendo puestos en su carrera, es ascendido a Teniente General, y obtiene el cargo de Capitán General de la VII Región Militar, en 1976. El mismo año, es nombrado además, jefe del Estado Mayor Central.
En 1976, entra en el Gobierno de España de mano del presidente Adolfo Suárez, ocupando los puestos que le otorgarían mayor reconocimiento por la sociedad española, el de Ministro de Defensa, y Vicepresidente del Gobierno. Este cargo lo volverá a desempeñar en la Legislatura Constituyente 1977-1979, y en la I Legislatura post-constitución.
La vicepresidencia de Gutierrez fue muy difícil. Los años de la transición fueron años muy duros, en los que los militares sobre todo, eran objetivo directo de la banda terrorista etarra. La población castrense y el ala más próxima a la dictadura, estaban muy disgustados con el vicepresidente, al que acusaban de blando y traidor, por no aplicar medidas con dureza para acabar con el terrorismo que tanto lastraba a la población militar. Tanto él como Suárez sufrieron duras críticas, que desembocaron en la ya conocida dimisión del gobierno de UCD en 1981, punto en el que Gutierrez abandona definitivamente sus cargos políticos.
Gutierrez Mellado protagonizó una de las escenas más representativas de la transición española. La tarde del 23 de febrero de 1981, cuando el Congreso de los Diputados votaba la investidura de Calvo Sotelo como presidente, se produjo un golpe de estado. Cuando el teniente-coronel Tejero irrumpió con sus hombres en el parlamento, el vicepresidente fue el unico miembro de la cámara que se levantó de su escaño. Plantó cara a los golpistas, y les exigió como Vicepresidente y como superior militar, que depusieran las armas. Los golpistas lanzaron entonces ráfagas disparos dentro del parlamento, y el propio Tejero zarandeó y trató de derribar al general en un forcejeo sin éxito. Este gesto, en la que un hombre de 70 años se enfrenta y resiste ante unos hombres armados, arriesgando su vida en defensa de la democracia, le otorga un gran prestigio y simbología popular.
Años más tarde, retirado de la vida política, vivió de cerca un fallecimiento por culpa de la droga, que causaba estragos en los 80. Por ello, decidió fundar en 1986 la FAD, Fundación de Ayuda contra la Drogadicción. En 1994 fue nombrado de forma honorífica Capitán General del Ejército, a la misma vez que el rey le nombra Marqués de Gutierrez Mellado.
El 15 de diciembre de 1995, mientras se dirigía a Barcelona para dar una conferencia en una universidad, patina en el hielo con su coche, en un punto negro de la A2 en la provincia de Guadalajara. El accidente, pese a no ser muy grave, le provocó una hemorragia pulmonar que acabó con su vida en el traslado en ambulancia hacia el hospital. Fue enterrado en Villaviciosa de Odón, localidad de la que era hijo predilecto.
Moría así, con 83 años, quien fue considerado pese a todo, uno de los principales padres y garantes de la restauración democrática en España.
