Trzecim, bardzo wymagającym warunkiem, który musiała spełniać nowa konstrukcja była możliwość przelotu bez międzylądowania z Kalifornii na Hawaje. Był to najdłuższy odcinek przerzutu wojsk w sytuacji zagrożenia wojennego prowadzący nad wodą. Przewidywano, że nowa konstrukcja ma być napędzana tylko jednym silnikiem. Warunki konkursu otrzymało 148 firm, 12 złożyło swoje projekty. 19 lutego 1965 roku do dalszej ich realizacji wybrano dwa, Lockheeda i Sikorsky (późniejszy Sikorsky S-66 i jego zmodernizowana wersja Sikorsky S-67 Blackhawk). 3 listopada tego samego roku US Army ogłosiła, że zwycięzcą konkursu AAFSS został projekt Lockheeda oznaczony przez wytwórnie jako CL-840. Nowa maszyna otrzymała również oznaczenie AH-56A Cheyenne, zgodnie z obowiązującą w armii zasadą nadawania śmigłowcom nazw indiańskich szczepów.