回到鹽湖城老家，尼爾曼試著玩起創投資本家的遊戲，最後以賠錢了事。一群加拿大人也跑來找他，他們想要以卡加利為根據地，創立一個區域型的航空公司。尼爾曼答應擔任他們的顧問，最後卻參與成為這家西部航空公司董事會的一員。尼爾曼甚至同意和其他董事一樣，每人出資20萬加幣購買新公司80萬股股份。尼爾曼協助草擬完成新航空公司的事業計劃書。
尼爾曼同時和摩裏斯航空前IT主管依凡斯合作，成立一家叫作OpenSkies的新公司，將一種不需訂位的電腦開立機票係統出售給各大航空公司。這項業務及參與加拿大新創的西部航空，都是尼爾曼在不違反競業條款的情形下，繼續參與航空事業。
所幸尼爾曼的事業計劃書非常吸引人，西部航空順利籌足了超過1億8,000萬美元，1996年2月正式營運。西部航空一炮而紅，他們的飛機在卡加利、艾德蒙頓、溫哥華、基隆拿、溫尼伯及維多利亞等城市間穿梭往返，幾乎班班客滿。尼爾曼也說服西部航空采用OpenSkies訂位係統。事實上，尼爾曼乃是以西部航空為實驗對象，測試一切可用於低成本顧客服務模型的技術與事業觀念，等到時機成熟，就可應用到美國航空市場，亦即他的下一個創業計劃。
西部航空與OpenSkies的營運都很成功。事實上，1998年10月，惠普科技以2,000萬美元買下OpenSkies，使該公司成為惠普旗下的一個事業群。同樣地，西部航空也是商業史上一個成功的範例。1999年6月，西部航空申請股票公開上市，以籌措足夠資金進一步成長。西部航空成為上市公司後，尼爾曼隨即出售他的持股，開始全力策劃成立一家新公司，準備在其競業條款時限屆滿後，立刻投入美國航空市場。
尼爾曼再度造訪曾幫助摩裏斯航空籌募資金的拉撒路，並提出請求，希望拉撒路能加入自己的創業陣容，攜手打造一家全新的航空公司。
「我笑了笑道：『誰需要一家航空公司呢？』但我很快就體認到，那絕非一個突發奇想的念頭。尼爾曼是凡事有計劃的人，是一個策略家，他的想法深深吸引了我。他的見解都經深思熟慮，例如：『我們專飛人口密集的地方。』我以為他在胡思亂想，但他愈詳加解釋，並指出確切的地點，我就看得愈清楚他那樣做的理由，不再恥笑他的構想。那是一個非常大的計劃，我們需要找很多人手，還有很多功課要研究。」
──拉撒路
「當時，他們暫定新公司的名字叫NewAir(新航)。其後兩年，尼爾曼及智囊團投入精心研擬事業計劃書、尋求財源、購置飛機、招募人員、建構組織，為將來成立新航空公司做好一切前置作業。尼爾曼有一個非常明確的使命：『以最低成本提供美國民眾最好的經濟艙飛航旅程服務。』」
──魏恩白蘭特
大衛?巴格是尼爾曼最初主動接觸的幾位人士之一。巴格在航空界服務多年，擁有豐富經驗。他答應尼爾曼作他的執行夥伴，負責處理日常例行事務。