Le programme Navaho fait partie initialement d'une série de programmes de recherche sur les missiles guidés lancés en 1946 par l'Armée américaine. North American remporte le contrat du missile à courte portée. Sous l'appellation MX-770, le programme initial avait pour objectif de développer un missile V2 doté d'ailes qui pourrait lancer une tête nucléaire à une distance de 800 km. C'était plus de deux fois la portée du V-2 et la charge utile était plus lourde. Les premières études montrèrent que des portées plus importantes pouvaient être atteintes et au cours des années qui suivirent les caractéristiques visées sont régulièrement améliorées : lanceur ailé lancé depuis le sol à un engin doté d'un statoréacteur d'une portée de 1850 km, puis engin aéroporté d'une portée de 2600 km et finalement missile de croisière propulsé par un statoréacteur et accéléré au départ par une fusée. Le dessin du Navaho est figé en juillet 1950 avec la commande par l'Armée de l'Air du système d'arme 104-1 d'une portée de 9 000 km.
Pour mettre au point le WS-104A, le programme NAVAHO comporte trois phases. La première porte sur le développement du North American X-10 un engin volant de portée plus limité qui doit permettre la mise au point des principales caractéristiques aérodynamiques, du guidage et de la phase terminale. Il est capable d'accélérer jusqu'à Mach 2 et peut voler sur une distance de 850 km. Une fois le X-10 mis au point et testé avec succès le développement du deuxième véhicule, le XSSM-A-4, Navaho II ou G-26 est lancé. Le G-26 est pratiquement un missile Navaho à échelle réduite. Lancé par un premier étage à ergols liquides, le G-26 monte à la verticale jusqu'à ce qu'il est atteint Mach 3 et une altitude de 15 km. Arrivé à ce point l'étage d'accélération est largué et le statoréacteur est allumé pour propulser le Navaho jusqu'à sa cible. Le G-26 est lancé à 10 reprises depuis Cape Canaveral entre 1956 et 1957.
La dernière version, le G-38 ou XSM-64A reprend le dessin G-26 mais est d'une plus grande taille. Il incorpore un grand nombre de nouvelles technologies : titane, moteur-fusée monté sur cardan, utilisation de la combinaison d'ergols kérosène/oxygène, transistors ... Aucun exemplaire ne volera et le programme est annulé avant que le premier exemplaire ne soit achevé. Les technologies développées seront utilisées sur les autres missiles dont le missile intercontinental Atlas et le système de guidage inertiel est utilisé par la suite dans le premier sous-marin nucléaire américain.
Le développement du premier étage de fusée du Navaho commence en 1947 en utilisant deux moteurs de V-2 rénovés. La même année, le moteur utilisé pour la phase II du programme est sélectionné : le XLR-41-NA-1 est une version simplifiée du moteur du V-2 réalisée avec des composants américains. Le moteur de la phase III, le XLR-43-NA-1 (également appelé 75K), met en œuvre une chambre de combustion cylindrique avec une platine d'injection développée pour le V2 mais restée expérimentale. Les ingénieurs de North American parviennent à maitriser les problèmes d'instabilité de combustion qui avaient empêché les allemands d'utiliser leur invention et le moteur est testé avec succès en 1951. Le moteur de la phase IV, XLR-43-NA-3 (120K), remplace la lourde paroi mal refroidie de l'engin allemand par un assemblage de tubes brasés, qui devient la méthode standard de refroidissement par régénération des moteurs-fusée américains. Deux moteurs de cette version sont utilisés sur le G-26 Navaho. Un moteur plus puissant, avec un refroidissement amélioré est développé pour la triple motorisation du G-38. Tous les composants d'un moteur-fusée moderne, en dehors de la tuyère, ont été développé dans le cadre du programme Navaho et seront exploitées sur les moteurs propulsant les fusées Atlas, Thor et Titan.