Třída Cheyenne se začala používat v 50. až 60. letech 24. století. Pravděpodobně měla nahradit v této době již vyřazované galaktické průzkumníky třídy Constellation. Oficiálně je třída klasifikována jako průzkumník (explorer). Třída se pravděpodobně příliš neujala, protože známe pouze jednu loď.
Design je v zásadě prakticky totožný s designem třídy Constellation. K talířové části jsou ze dvou stran připevněny pylony, přičemž každý nese 2 gondoly. Délka činí 362 metrů. Loď je konstruována tak, aby v případě nouze bylo možné loď rozdělit. První část pak tvoří talířová část, druhou část pylony a gondoly.
Cheyenne je další ze tříd, které byly vytvořeny pro epizodu TNG: The Best of Both Worlds. V záběrech na vraky lodí zničených borgskou krychlí loď této třídy ale nevidíme, přestože byl model vyroben (viz. článek Bitva u Wolf 359). Na obrazovce jsme tedy tuto třídu nikdy neviděli. Model lodi (obrázek níže) byl vyroben z částí modelu U.S.S. Enterprise-D. Aby bylo jednoznačné, že třída je menších rozměrů než třída Galaxy, pro palubu s můstkem byl použit můstek z modelu třídy Galaxy jiného měřítka (1:1400). Další obrázky modelu naleznete v galerii.
Cheyenne je kmen severoamerických indiánů, obývajících Velké pláně. Dnes žijí především v Montaně a Oklahomě.
