Partyband dannet i Stokmarknes i 1982 av Kai Kiil (vokal, gitar), Rudi Høynes (trommer, vokal), Royer Larsen (bass) og Alf Eriksen (tangenter, vokal). Høynes og Larsen kom fra Zoo, mens Kiil hadde lang fartstid i diverse band. I 1983 spilte Banana Airlines inn en ny versjon av Olle Adolphsons «En glad calypso om våren» som Per Asplin hadde hatt stor suksess med i 1959. Singelen en ble en landeplage, og det påfølgende albumet På vingene en storselger. «Yes We have No Bananas» toppet Norsktoppen tre uker i 1983.

Platekritikerne delte ikke publikums begeistring for Banana Airlines, som måtte tåle mye pepper i pressen. Spesielt hardt gikk det ut over Kai Kiil og den sangstilen han hadde lagt seg til, hvor han på freidig vis etterapet en innvandrers begrensede taleferdigheter. Rasisme, mente noen; uskyldig, mente andre. «Du må tåle en fleip,» sang Kai Kiil.

Roy Stenersen (gitar, vokal) ble hentet inn som femte medlem før innspillingen av LP nummer to, På nye eventyr (1984). Herfra ble «Nordmenn er gale» en ny slager, dog ikke i samme grad som «En glad calypso om våren». Året etter ble Alf Eriksen etterfulgt av Sverri Dahl (tangenter, vokal), og dermed var det overvekt av Zoo-medlemmer i bandet. Tredje album Vi kommer snart på hjem (1985) ble i likhet med de to foregående produsert av Jan Paulsen.

Det tok tre år før neste plate kom. Innen den tid hadde Larsen overlatt bassen til Dag Christensen, som deltok på to LP-er før han forlot selskapet. Per Sveinson ble hentet inn som produsent på Flyr igjen (1988), og blant gjestende musikere her var Bent Bredesen, Ole Edvard Antonsen og Sigurd Jansen. Resultatet var gruppens mest varierte meny musikalsk sett.

Nytt rabalder i pressen ble det i 1989 da Banana Airlines ga ut «Samii-rappi». Gruppen ble beskyldt for å drive med hetsing av samene, til tross for at Nils Mathis Bæhr deltok høyst frivillig og joiket av hele sitt hjerte. Albumet som «Samii-rappi» var hentet fra – Hjelp, vi flyr! (1989), produsert av Nils B. Kvam – inneholdt for øvrig en norsk versjon av Pete Seegers «If I Had A Hammer», hvor Kai Kiil sang «Hvis æ hadde tenner».

Etter noen års platepause tok Banana Airlines av igjen med Kommer plutselig tilbake (1994), som besto av nye og gamle sanger i ny tapning. Siden forrige flytur hadde Kiil rukket å gjøre suksess i Barne-TV som den rampete Vaktmester’n. Gruppen fulgte opp med Går i lufta i 1996, men deretter tok det fem år før neste plate kom. På Fest sikkerhetsbeltet (2001) var Stig Andreassen kommet med som ny bassist, mens produsent Tomas Siqveland bidro med gitar, bass og fløyte på enkelte spor.

Banana Airlines’ medvirkning i spillefilmen Kill Buljo (2007) førte til fornyet interesse for bandet.