アメリカ陸軍の航空部門であるアメリカ陸軍航空隊は、第二次世界大戦が始まる5年前の1934年5月に超長距離大型爆撃機開発計画「プロジェクトA」を発足させた。これは1トンの爆弾を積んで8,000km以上を飛ぶことができる爆撃機を作る計画で、アメリカ陸軍航空軍司令官ヘンリー・ハップ・アーノルド将軍を中心とし長距離渡洋爆撃を想定していた。B-29はこの構想の中から生まれた機体で、1938年に完成した試作機（ボーイングXB-15）から得られた種々のデータや、新しい航空力学のデータをもとに設計製作された。そして1939年9月1日のナチス・ドイツ軍によるポーランド侵攻の日、アメリカのキルナー委員会は、陸軍は今後5年間で中型・若しくは大型の戦略爆撃機の開発を最優先とすべきとの勧告をしている。

1939年11月、行動半径2000マイルでB-17、B-24に優る四発爆撃機の試作要求が提出される[28]。1940年6月27日、5機が予備発注される[28]（XB-29）。1941年5月にはアメリカ陸軍よりボーイング社に250機を発注する意向が通告され、ボーイング社はウィチタで広大な新工場の建設に着手し、大量の労働者を確保した。1941年9月6日にアメリカ陸軍とボーイング社の間で正式な発注の契約が締結されたが、この契約を主導したアメリカ陸軍物資調達本部のケネス・B・ウルフ准将は、まだ試験飛行すらしていない航空機に対する莫大な発注に「30億ドルの大ばくち」だと言っている。しかし12月8日に日本軍による真珠湾攻撃でアメリカの第二次世界大戦への参戦が決定すると、この発注は500機に増やされ、1942年2月10日にはさらに1,600機に増やされた[29]。

1942年9月21日、B-29が初飛行[28]。試作第一号機のXB-29-BOがエディ・アレンと彼のチームによって飛行した。アレンは試作二号機（製造番号41-003）のテスト飛行も担当したが、1943年2月18日、テスト飛行中のエンジン火災で操縦不能となって食肉加工工場の五階建てビルに衝突、アレンを含む11名のB-29クルー、工場にいた19名の民間人、消火活動中の消防隊員1名の合計31名が死亡、B-29最初の事故喪失機となった。議会が発足させた調査委員会（委員長は当時上院議員だったハリー・S・トルーマン）は、急ピッチな開発方針のもと、エンジンメーカーのライト社が質より量優先の生産体制をとり、エンジンの信頼性低下を招いたことを明らかにし、メーカーと航空軍に対し厳重に改善を勧告した。しかし、これらの諸調査が行われている間はB-29の全計画は全く進まず、スケジュールが遅れることとなった[30]。