1952年12月27日、日本ヘリコプター輸送として第２次世界大戦により壊滅したわが国の定期航空事業を再興することを目的に使用事業・旅客輸送・郵便輸送を行う航空会社として設立された。1953年2月に、ヘリコプターを用いて営業を開始し、5月には不定期航空運送事業免許、10月には定期航空運送事業免許を取得。1953年12月15日に、デハビランドダブにより東京大阪間の貨物郵便輸送を開始。1954年2月1日には、同じくダブによる東京大阪間の定期旅客便の運航を開始した。1955年には、DC-3就航を機にスチュワーデスを初めて採用するなど徐々にその体制を整えていった。
1957年12月1日、日本ヘリコプター輸送は、国内ローカル線を運航する航空会社は一社にするという政府の方針により、大阪の航空会社極東航空（1952年設立）と合併するために、社名を全日本空輸と改称し、極東航空の路線を引き継いだ。1958年3月1日には全ての手続きが終了し、正式に合併した。機体塗装・制服とも一新しての再出発。しかし、デハビランドダブやヘロンのような小型旅客機で途中いくつもの空港を経由しながら飛ぶ全日空と、DC-4のような大型機で直行便を飛ばす日本航空（現日本航空インターナショナル）との格差は開くばかりだった。純民間で経営も苦しい全日空には、新機材の投入も容易なことではなかったが、生き残るには新機種の導入は不可避であることから、全日空は、翌1959年に快適な与圧キャビンを備えたコンベア440を、1960年、61年には、ターボフロップ機Ｆ−２７フレンドシップ（1961年6月）とバイカウント（バイカウント744型：1960年8月，バイカウント828型：1961年6月）といった具合に最新鋭機を次々に投入。日本航空との新機材投入合戦、スピード競争が加熱する。このころになると遂に両者とも国内線へのジェット機投入を模索し始めるが、あまりの競争の過熱ぶりに政府が介入し、両社とも同じジェット機を投入することで合意し、ボーイング727を選定。ところが、全日空が1959年以降レシプロ機に代わりターボフロップ機の導入を進めたことで、国内線にレシプロ機を用いていた日本航空が受けた打撃は大きく、急遽、短距離国際線機材として予定していたコンベア880を国内線に投入してきた。これにより自社のボーイング727の受領まで待てなくなった全日空は、1964年4月、リースでボーイング727を入手し、直ちに路線に投入し応酬した。自社発注のボーイング727を受領し導入したのは1965年3月のことであった。
全日空は、日本航空との激しい新機材投入合戦の最中の1963年11月、藤田航空を吸収合併し現在の体制となった。1965年7月には国内ローカル線の主力機として国産旅客機YS-11（オリンピア）を導入、1969年5月にはボーイング737の導入を機に機体塗装をモヒカンルックに変更。その後も全日空は、新機材を積極的に導入するかたわら、国内線路線網を広げていく。そして1971年2月には、東京−香港間で念願の国際線チャーター便の運航開始を果たし、1972年8月には、東京、大阪両証券取引所市場第二部から市場第一部に上場を果たすなどこれまでの社員の苦労が結実し始めた。70年代には全日空も大量輸送時代を迎える。1973年12月にはロッキードＬ１０１１トライスターを導入。1978年12月にはボーイング７４７ＳＲを就航させた。これにより全日空の輸送力は格段に向上する。1983年6月、ボーイング767を導入、創立３０周年を迎えたこともあり、機体塗装を現在のトリトンブルーに変更、この変更により、日本ヘリコプター輸送設立以来親しまれたダビンチマークが機体から姿を消すこととなった。
1985年末には、「４５／４７体制」が廃止され、それまで国際線チャーター便で細々と国際線の実績を積んできた全日空は、念願の国際線定期便の開設にこぎ着ける。1986年3月3日の東京−グアム線の開設を皮切りに、同年7月にはロサンゼルス・ワシントンＤＣ線開設。以降アジア・オセアニア・ヨーロッパへ順次進出した。機材面でも1990年11月にはボーイング747-400、1991年3月には、エアバスA320、1995年12月には、ボーイング777、1998年3月エアバスA321を導入するなど新規機材の導入に積極的に取り組んだ。1999年10月には次第に熾烈さを増す国際競争に対応するために、航空連合スターアライアンスに加盟した。
2002年10月2日、ライバルの日本航空と日本エアシステム（現日本航空インターナショナル）が経営統合し、持ち株会社日本航空システム（2004年6月、日本航空に改称）が発足した。これに伴い、日本航空、日本エアシステムは日本航空システムの連結子会社となり、段階的に統合され、業務別に再編成されることになった。以後国内航空業界は全日空との２強時代を迎えた。全日空にとっては、国内ローカル線を中心に広い路線網を築く日本エアシステムと国際線に圧倒的な路線網を持つ日本航空の経営統合の衝撃は大きなものであった。
2004年4月1日、経営統合した日本航空インターナショナル（旧日本航空）と日本航空ジャパン（旧日本エアシステム）が、便名をJALで統合したことに対抗し、全日空も子会社（エアーニッポン・エアーニッポンネットワーク）の便名をANAで統合した。
 |  |
|
| コンベア440 撮影：戸田保紀氏1965年羽田空港 | バイカウント 撮影：戸田保紀氏1966年羽田空港 |
|
 |  |  |
| 旧塗装のボーイング747 撮影：外山智士1987年9月27日大阪国際空港 | ボーイング727(JA8349) 撮影：外山智士大阪国際空港 | ロッキードL1011トライスター 撮影：外山智士1989年3月25日大阪国際空港 |
 |  |  |
| YS-11(JA8722) 撮影：外山智士1989年5月3日大阪国際空港 | ボーイング767-300(JA8273) 撮影：外山智士1999年5月大阪国際空港 | エアバスA320 撮影：外山智士1999年5月大阪国際空港 |