Pada tanggal 25 Desember 1949, wakil dari KLM yang juga teman Presiden Soekarno, Dr. Konijnenburg, menghadap dan melapor kepada Presiden di Yogyakarta bahwa KLM Interinsulair Bedrijf akan diserahkan kepada pemerintah sesuai dengan hasil Konferensi Meja Bundar (KMB) dan meminta kepada beliau memberi nama bagi perusahaan tersebut karena pesawat yang akan membawanya dari Yogyakarta ke Jakarta nanti akan dicat sesuai nama itu.

Menanggapi hal tersebut, Presiden Soekarno menjawab dengan mengutip satu baris dari sebuah sajak bahasa Belanda gubahan pujangga terkenal, Raden Mas Noto Soeroto di zaman kolonial, Ik ben Garuda, Vishnoe's vogel, die zijn vleugels uitslaat hoog boven uw eilanden ("Aku adalah Garuda, burung milik Wisnu yang membentangkan sayapnya menjulang tinggi diatas kepulauanmu")

Maka pada tanggal 28 Desember 1949, terjadi penerbangan yang bersejarah yaitu pesawat DC-3 dengan registrasi PK-DPD milik KLM Interinsulair terbang membawa Presiden Soekarno dari Yogyakarta ke Kemayoran - Jakarta untuk pelantikannya sebagai Presiden Republik Indonesia Serikat (RIS) dengan logo baru, Garuda Indonesian Airways, nama yang diberikan Presiden Soekarno kepada perusahaan penerbangan pertama ini.

Garuda Indonesia berawal dari tahun 1940-an, di mana Indonesia masih berperang melawan Belanda. Pada saat itu, Garuda terbang jalur spesial dengan pesawat DC-3.

Pada tanggal 26 Januari 1949 dianggap sebagai hari jadi Garuda Indonesia. Pada saat itu nama maskapai adalah Indonesian Airways. Pesawat pertama mereka bernama Seulawah atau Gunung Emas, yang diambil dari nama gunung terkenal di Aceh. Dana untuk membeli pesawat ini didapatkan dari sumbangan rakyat Aceh, pesawat tersebut dibeli seharga 120,000 Dollar Malaya yang sama dengan 20 kg emas. Maskapai ini tetap mendukung Indonesia sampai revolusi terhadap Belanda berakhir. Garuda Indonesia mendapatkan konsesi monopoli penerbangan dari Pemerintah Republik Indonesia pada tahun 1950 dari Koninklijke Nederlandsch-Indische Luchtvaart Maatschappij, perusahaan penerbangan nasional Hindia Belanda. Garuda pada awalnya adalah hasil joint venture antara Pemerintah Indonesia dengan maskapai Belanda, Koninklijke Luchtvaart Maatschappij (KLM). Pada awalnya, Pemerintah Indonesia memiliki 51% saham dan selama 10 tahun pertama, perusahaan ini dikelola oleh KLM. Karena paksaan nasionalis, KLM menjual sebagian dari sahamnya pada tahun 1953 ke pemerintah Indonesia.

Pemerintah Burma banyak menolong maskapai ini pada masa awal maskapai ini. Oleh karena itu, pada saat maskapai ini diresmikan sebagai perusahaan pada 31 Maret 1950, Garuda menyumbangkan sebuah pesawat DC-3 kepada Pemerintah Burma. Pada mulanya, Garuda memiliki 27 pesawat terbang, staf terdidik, bandara dan jadwal penerbangan, sebagai kelanjutan dari KNILM. Ini sangat berbeda dengan perusahaan-perusahaan pionir lainnya di Asia.

Pada tahun 1953, maskapai ini memiliki 46 pesawat. Tahun 1956 mereka mengangkut jamaah haji dan membuat jalur penerbangan pertama ke Mekkah.

Tahun 1960-an adalah era kemajuan pesat Garuda. Pada tahun 1960, Garuda mendatangkan tiga pesawat turboprop Lockheed L-188C Electra. Ketiga pesawat baru itu masuk dinas aktif pada bulan Januari 1961 serta diberi nama "Pulau Bali", "Candi Borobudur" dan "Danau Toba", tiga tujuan wisata Indonesia yang paling dikenal dunia luar. Di tahun yang sama, Garuda membuka rute penerbangan menuju Hong Kong. Garuda memasuki era jet di tahun 1964 dengan datangnya tiga pesawat baru Convair 990A yang diberi nama "Majapahit", "Pajajaran" dan "Sriwijaya", nama-nama kerajaan kuno di Indonesia, dan menjadi maskapai pertama di Asia Tenggara yang mengoperasikan pesawat jet subsonik. Saat itu, jet bermesin empat Convair 990 merupakan pesawat berteknologi canggih dan memiliki kecepatan tertinggi dibandingkan pesawat-pesawat lain yang sejenis, seperti Boeing 707 dan Douglas DC-8[6]. Dengan pesawat ini pula Garuda kemudian membuka penerbangan antarbenua dari Jakarta ke Amsterdam melewati Kolombo, Bombay, Roma, dan Praha. Di tahun 1966, Garuda kembali memperkuat armada jetnya dengan mendatangkan sebuah pesawat jet baru, yaitu Douglas DC-8. Sementara, pada akhir tahun 1960-an, Garuda membeli sejumlah pesawat turboprop baru, Fokker F27. Pesawat ini datang secara bertahap mulai tahun 1969 hingga 1970 dan dioperasikan untuk penerbangan domestik.

Pada tahun 1970-an Garuda Indonesia membeli beberapa jenis narrow-body jet yaitu McDonnell-Douglas DC-9 dan Fokker F28 serta pesawat jenis turboprop Fokker F27 (sebagai sarana transisi para pilot dan kru pendukung ke F28 yang bermesin turbojet) untuk penerbangan domestik. Pada 1973, maskapai ini mulai membeli pesawat badan lebar McDonnell Douglas DC-10-30 untuk penerbangan internasional jarak jauh, seperti ke Eropa, sementara Douglas DC-8 digunakan untuk penerbangan ke Asia dan Australia, dan akhirnya dipensiunkan sekitar akhir 1970-an. Sementara pada 1980-an mengadopsi perangkat dari Airbus, seperti A300 dan mulai membeli Boeing 747-2U3B untuk menambah penerbangan ke Eropa dan Amerika Serikat. Garuda merupakan operator terbesar Fokker 28, sekitar 63 unit pernah dioperasikan. Garuda juga merupakan konsumen perdana (launch customer) dari Airbus A300B4-220FFCC (varian A300 perdana dengan kru kokpit 2 orang)

Dalam tahun 1990-an, Garuda membeli 9 unit McDonnell-Douglas MD-11 (1991), Boeing 737 seri -300 , -400, dan -500 (tahun 1992, untuk menggantikan DC-9), serta Boeing 747-400 (tahun 1994, 2 dibeli langsung dari Boeing, 1 disewa, bekas Varig) dan Airbus A330-300 (1996). Tetapi, pada masa ini Garuda mengalami dua musibah, yang pertama, di Fukuoka, Jepang, dan yang terburuk , dan yang juga merupakan tragedi terburuk dalam sejarah penerbangan Indonesia, adalah pada tahun 1997, dimana sebuah A300 jatuh di Sibolangit, Sumatera Utara. menewaskan seluruh penumpangnya. Maskapai ini pun mengalami periode ekonomi sulit, karena, pada tahun yang sama Indonesia terkena Krisis Finansial Asia, yang terjadi pada tahun yang sama. Setelah itu, Garuda sama sekali tidak terbang ke Eropa maupun Amerika (meskipun beberapa rute seperti Frankfurt, London dan Amsterdam sempat dibuka kembali, namun akhirnya kembali ditutup. Rute Amsterdam ditutup tahun 2004). Tetapi, dalam pertengahan tahun 2000-an ini maskapai ini telah dapat mengatasi masalah-masalah di atas dan dalam keadaan ekonomi yang bagus[7].

Memasuki tahun 2000an, maskapai ini membentuk anak perusahaan bernama Citilink, yang menyediakan penerbangan biaya murah dari Surabaya ke kota-kota lain di Indonesia. Namun, Garuda masih saja bermasalah, selain menghadapi masalah keuangan (Pada awal hingga pertengahan 2000an, maskapai ini selalu mengalami kerugian), Beberapa peristiwa internasional (juga di Indonesia) juga memperburuk kinerja Garuda, seperti Serangan 11 September 2001, Bom Bali I dan Bom Bali II, wabah SARS, dan Bencana Tsunami Aceh 26 Desember 2004. Selain itu, Garuda juga menghadapi masalah keselamatan penerbangan, terutama setelah jatuhnya sebuah Boeing 737 di Yogyakarta ketika akan mendarat. Hal ini mengakibatkan sanksi Uni Eropa yang melarang semua pesawat maskapai Indonesia menerbangi rute Eropa. Namun, setelah perbaikan besar-besaran, tahun 2010 maskapai ini diperbolehkan kembali terbang ke Eropa, setelah misi inspeksi oleh tim pimpinan Frederico Grandini[8].yaitu rute Jakarta - Amsterdam. Rute Eropa lain seperti Paris, London, dan Frankfurt juga dipertimbangkan untuk dibuka kembali, tergentung keadaan perekonomian Indonesia kelak.