Семья и образование
Родился в семье, принадлежавшей к среднему классу, остался сиротой в возрасте восьми лет. В 1929 поступил в Главную военную академию в Сарагосе, директором которой был Франсиско Франко. После окончания академии (в 1933; первым в выпуске) был произведён в лейтенанты артиллерии.
Участие в гражданской войне
В начале гражданской войны, в июле 1936, вместе со своим полком выступил против правительства республики, был арестован и заключён в тюрьму, из которой бежал. Нашёл убежище в одном из иностранных посольств в Мадриде, затем смог добраться до территории, контролируемой националистами. Оттуда, уже по поручению франкистской разведки, тайно вернулся в республиканскую зону, где занимался агентурной деятельностью до окончания войны. За успешную работу в 1938 был произведён в капитаны.
Служба в армии франкистской Испании
После окончания войны продолжил службу в армии, в 1942 получил диплом офицера Генерального штаба. Был произведён в майоры, преподавал в артиллерийской школе (Escuela de Aplicaci?n y Tiro de Artiller?a). Специалист в области разведки, долгое время работал в Генеральном штабе, занимался переводами с английского языка. С 1957 — подполковник, с 1965 — полковник. Постепенно стал более критично относиться к франкистскому режиму. С 1970 — бригадный генерал. Занимал ответственные должности в Высшем центре исследований национальной обороны (CESEDEN) и Генеральном штабе, был сотрудником либерально настроенного интеллектуала, генерал-лейтенанта Мануэля Диес-Алегрия. С 1973 — дивизионный генерал. С 1975 — командующий войсками в Сеуте (Африка) и правительственный делегат на этой территории. В том же году скончался генералиссимус Франко, и вскоре после этого карьера генерала резко ускорилась.
Сторонник демократии
Молодому королю Хуану Карлосу I, только что вступившему на престол, нужен был военачальник, способный на проведение военных реформ с целью преобразования франкистской армии в вооруженные силы современного демократического государства. В марте 1976 Гутьеррес Мельядо был произведён в генерал-лейтенанты и назначен на должность генерал-капитана (командующего) седьмого военного округа со штабом в Вальядолиде (должность генерал-капитана в испанской армии существовала наряду с одноименным воинским званием, которое, согласно принятым в 1975 правилам, могло присваиваться только королю как главнокомандующему). Уже в июне 1976 он стал начальником Генерального штаба, а в сентябре того же года — первым заместителем председателя правительства Адольфо Суареса по вопросам обороны. После всеобщих выборов 15 июня 1977 сохранил этот пост, который занимал до 1981.
В рамках реформы вооружённых сил генерал Гутьеррес Мельядо был инициатором создания в 1977 министерства обороны, которое объединило три прежних министерства — военное, морское и авиации. В 1977—1979, наряду с постом первого заместителя председателя правительства, являлся и министром обороны (последующие руководители этого ведомства были гражданскими лицами). Продвигал на ключевые посты либеральных военачальников, игнорируя традиций назначений в строгом соответствии с принципом старшинства. Реорганизовал Генеральный штаб и создал новую разведывательную организацию. Был сторонником деполитизации вооружённых сил. Его деятельность вызвала резкое неприятие со стороны наиболее последовательных сторонников франкистского режима, которые называли его масоном и обвиняли в том, что он был двойным агентом в годы гражданской войны (если бы такие обвинения имели под собой основания, то генерал не смог бы сделать военную карьеру при режиме Франко).