Авиакомпания ValuJet Airlines была основана в 1992 году. Первый регулярный рейс под номером 901 был выполнен 26 октября 1993 года из Атланты в Тампу в рамках введённых маршрутов из Атланты в Орландо, Тампу и Джэксонвилл. Первоначально воздушный парк перевозчика составлял один самолёт Douglas DC-9, ранее принадлежавший основному конкуренту — авиакомпании Delta Air Lines. ValuJet Airlines возглавили ветераны отрасли пассажирских перевозок, включая одного из основателей компании и её генерального директора Роберта Придди, который в своё время создал целый ряд успешных американских авиакомпаний таких, как Atlantic Southeast Airlines, Air Midwest Airlines и Florida Gulf Airlines. Два других соучредителя Морис Гэллахер и Тим Флинн ранее развивали авиакомпанию WestAir, которая затем была продана региональному перевозчику Mesa Airlines. К концу 1993 году к команде топ-менеджеров ValuJet Airlines присоединился бывший президент Continental Airlines и Flying Tiger Льюис Джордан.

В течение 1993 года воздушный флот авиакомпании вырос до 15 пассажирских лайнеров, а в следующем году ValuJet Airlines стала публичной компанией, разместив собственные акции на фондовой бирже NASDAQ. ValuJet Airlines вошла в историю индустрии пассажирских перевозок Соединённых Штатов, как авиакомпания с самым стремительным развитием — всего через год после своего первого рейса компания получила 21 миллион долларов США чистой прибыли (по итогам 1994 года). В октябре 1995 года авиакомпания разместила заказ на 50 реактивных самолётов MD-95, которые после слияния McDonnell Douglas с корпорацией Boeing стали известны под именем Boeing 717—200. После заключения договора ValuJet Airlines стала первой бюджетной авиакомпанией мира, являвшейся площадкой для обкатки нового пассажирского лайнера. До поставки MD-95 ValuJet Airlines активно приобретала использованные в других компаниях самолёты с целью временного сокращения кредитных издержек. Эта особенность ведения бизнеса привела к тому, что средний возраст воздушного парка составил 26 лет, что стало одним из наихудших показателей среди остальных авиакомпаний США и в дальнейшем явилось одной из главных причин банкротства перевозчика.