Als 17 anys va ingressar a l'acadèmia militar de Saragossa i va lluitar a la Guerra Civil en el bàndol nacional. Va patir presó, va demanar asil a una ambaixada i va ser agent clandestí al Madrid republicà. Va assolir el rang de general el 1970 i el de general de divisió el 1973. Fou ascendit a tinent general, nomenat posteriorment capità general de la VII Regió el març del 76 i el juny d'aquell any nomenat cap de l'Estat Major Central.

Llavors ja se’l considerava un militar oberturista, pròxim al general Manuel Díez Alegría, destituït per Franco de cap de l'Estat Major Central pel seu reformisme polític i per la seva relació amb el polític socialdemòcrata madrileny Antonio García López. García López, durant anys, va intentar connectar amb els generals més oberturistes i convèncer-los de la necessitat d'un sistema democràtic.

El setembre de 1976 Suárez el va cridar per substituir el tinent general Fernando de Santiago. Va ser llavors vicepresident primer per a Assumptes de la Defensa i va continuar ocupant el càrrec fins a la dimissió d'Adolfo Suárez el 1981. Durant aquest temps Gutiérrez Mellado va tenir un paper transcendental en la despolitització de l'Exèrcit i en l’acatament de l'ordre constitucional per part d’aquest. El febrer de 1981 va plantar cara als guàrdies civils que, a les Corts i comandats pel coronel Tejero, van intentar fer un cop d'Estat. Va ser una actuació que tothom va poder veure a TVE i per la qual es va guanyar un gran respecte de tots els sectors polítics. Sense Gutiérrez Mellado, la Transició hauria estat, sens dubte, molt més difícil. Va morir el 15 de desembre de 1995 en un accident de trànsit a la província de Guadalajara.