1994年元月，尼爾曼開始到西南航空服務，擔任執行副總裁一職，兼任主管指導委員會委員。尼爾曼被告知，他可以全力爭取西南航空任何一項職位──想當然他會希望凱勒赫退休後取而代之。這個意圖，自然讓尼爾曼和管理團隊其他成員產生一些摩擦。
「那隻是我的一個夢想。我單純的假設，我去了達拉斯，便可享受一頓愛的饗宴。然而事情總是沒有我們想象的那樣簡單。」
──尼爾曼
尼爾曼到各處視察後發現，西南航空確實需要進行大幅度革新。而且，一如以往，他並未壓抑自己不講真話。他極力主張西南航空應實施劃位製、引進電子開票係統，不要再透過旅行社銷售機票。尼爾曼過去在小機構，一有改革念頭，就可立即付諸實施。如今橫亙在他麵前的，是西南航空公司的管理製度，一個難以周旋的龐然大物。盡管如此，尼爾曼仍然堅持己見，常闖入未被邀請的會議，大聲疾呼要求進行改革。
「基本上，他們希望給我兩年時間，讓我默默坐在自己位子上，聆聽他人的想法。我卻經常說溜了嘴：『你們為什麼要這樣做？』我發現，公司召開的例行主管會報既冗長又沒有重點，他們可以針對客機活動梯操作員懷孕該如何處理的問題，花兩個小時討論，卻找不到結論。我實在忍不住了，起身吼道：『我們能不能趕緊作出決定，好進行下一個議題？』我發覺，我是廁身在一家成功企業裏的創業者，是在一個不需要革命的地方想要帶頭革命的人。」
──尼爾曼
尼爾曼在西南航空待了五個半月就離職了。為讓自己順利脫身，他簽署了一項競業條款。該條款說明，他在離職的五年內，不得從事與美國國內航空業有關的事業。
「現在回想起來，我就覺得很可笑。尼爾曼是那樣地聰明，那樣地求好心切，才思又是那樣地敏捷。我認為，他的步調對我們來說太快了。我認為，我們等於是要求他隻需閉著眼睛睡覺。他是真正的革命家。挑戰愈大，尼爾曼就愈感興奮。我們以追求穩健、保守的成長見長，他卻走在我們前麵光年之遠。」
──巴瑞特
「創立摩裏斯航空時，我參與所有大小事務。某架飛機發生故障，我一定知道。我會忙著打電話調零件，我對公司營運可說是投入全部的心力。到了西南航空，我卻每天按時上下班，晚上幾乎無事可做。於是，我去了飛機調度場四處看看。我發現，其實有各式各樣的惡劣天候，不論是聖路易起了冰風暴或暴風雪，或其他地方發生雷電交加的暴風雨，都會對飛航造成嚴重威脅。我感覺很不安，心想：『我懷疑凱勒赫可能不知道這些事。』我若到樓上辦公室找他，他可能關心的隻是公司的未來，一點也不擔心某個營運日可能發生的狀況。因此，我從此學到了寶貴的一課：如果我有機會創設另一家航空公司，我一定會盡全力和基層人員攜手合作，他們是我可以信賴的人。我會對他們說：『我把飛機營運的事交給你們，我們每個月會針對飛機性能運轉情形定期檢討，以確保我們朝正確的方向前進。』」
──尼爾曼
有趣的是，就在此時，醫生診斷出尼爾曼罹患了注意力缺陷症。這是一種神經性疾病，病征是容易衝動、易怒、注意力不集中，有高危險行為傾向等；這些正是尼爾曼在西南航空的寫照。盡管如此，尼爾曼並無怨言。與西南航空分道揚鑣後，尼爾曼覺得自己得到了自由，可以去做不一樣的事。然而，他的身體裏流的全是航空事業的血液。那一紙競業條款，表示他必須在航空領域界限以外的地方熬五年。對尼爾曼來說，什麼事都不做顯然非他所願。