A légitársaságot 2005-ben alapították, és 2006 áprilisában fejezte be az első tanúsítási eljárást, amikor a portugál polgári légiközlekedési hatóság, az ANAC kiállította számára az üzemben tartási engedélyt. A légijármű-üzemeltetési engedély megszerzése óta a fuvarozó megszerezte az összes jogszabályban előírt EU-OPS (a kereskedelmi célú merevszárnyú utas- és teherszállító légi közlekedés minimális biztonsági és kapcsolódó eljárásait meghatározó rendeletek) és az Európai Unió Biztonsági Ügynökségének (EASA) jóváhagyását. Emellett 2011 szeptemberében megkapta az IATA működési biztonsági audit (IOSA) tanúsítványát is.
A Hi Fly első repülőgépe egy Airbus A330-300-as volt, amelyet korábban az Air Luxor üzemeltetett (amely ugyanannak a családnak a tulajdonában volt, amely most a Hi Fly tulajdonosa, mielőtt eladták és bezárták). A repülőgép nemrégiben a Belga Fegyveres Erők légi komponensével állt szerződésben 2013 végéig. Ezt követően 2008-ban két A310-300-as került forgalomba, amelyeket az Oman Airnek adtak bérbe, és a légitársaság első hosszú távú útvonalait (London/Heathrow és Bangkok felé) teljesítették.
Ezután 2008-ban és 2009-ben új repülőgépeket szállított az Airbus: egy A330-200-ast és két A340-500-ast, utóbbit mintegy 5 évig a nigériai Arik Air nevében használták a Lagos és New York/John F. Kennedy közötti útvonalon, az ő színeire festve, amíg a Hi Fly 2015 tavaszán vissza nem vette a repülőgépeket. Azóta további A330-asokat és A340-eseket is beszereztek, köztük négyet 2013-ban. 2014 februárjában a Hi Fly felvásárolta első keskeny törzsű repülőgépét, egy A321-200-ast, amelyet a belga hadseregnek adtak bérbe a korábbi A330-300-as helyett.
2013 márciusának elején létrehozták a Hi Fly Malta-t, a Hi Fly máltai leányvállalatát, amely Airbus A340-600-asokból álló flottát üzemeltet; ez a részleg jelenleg egy pár A340-300-asnak ad otthont.
A Hi Fly központja Lisszabon belvárosában található. Itt található az összes vállalati iroda, valamint a repülési és földi üzemeltetési, műszaki és karbantartási, biztonsági, kereskedelmi, kereskedelmi, pénzügyi, adminisztrációs és minőségellenőrzési részlegek. A repülőgép- és kabinszemélyzet számára oktatótermek is találhatók. A lisszaboni repülőtéren található egy karbantartó hangár, amelyet a MESA, a csoport egyik leányvállalata üzemeltet.
2015 májusában a szaúd-arábiai Saudia légitársaság azonnali hatállyal felmondta a Hi Fly-val kötött hosszú távú lízingszerződését két Airbus A330-asra vonatkozóan, miután az egyiket az izraeli Ben Gurion repülőtéren a Saudia teljes festésében látták. Izraeli médiajelentések szerint az A330-as az Israel Aerospace Industries MRO-szárnyánál, a Bedeknél volt rutinszerű karbantartáson, a Hi Flyval kötött szerződés értelmében. Az Arab News azonban arról számolt be, hogy bár a repülőgép akkoriban nem teljesített kereskedelmi járatot a Saudia számára, a szaúdiak azt állították, hogy a Hi Fly megsértette a szerződés feltételeit azzal, hogy a gépet egy olyan országba küldte, amellyel Szaúd-Arábiának nincsenek hivatalos diplomáciai kapcsolatai. A Hi Fly ezt követően visszaadta a repülőgépet a bérbeadójának a megmaradt A330-300-asával együtt.
A Hi Fly teszteli, hogy az egyszer használatos műanyag helyett komposztálható anyagokkal szolgálják ki az utasokat az étel- és italkínálatban. Egy 2018. decemberi járat volt az első, amelyen nem használtak egyszer használatos poharakat, evőeszközöket és edényeket.
2019. június 29-én a Hi-Fly légitársaság egyik, az orlandói repülőtérre visszatérő A340-es repülőgépe a repülőtér kifutópályájának több mint 84%-án lerakta az üzemanyagát. A gép hidraulikai problémákkal küzdött, és kénytelen volt visszatérni. Nem volt világos, hogy a pilóta miért dobta ki az üzemanyagot a kifutópályára.