Новая авиакомпания должна была стать альтернативой национальному перевозчику Icelandair. Однако, у Iceland Express не было своих самолётов и весь флот она брала в лизинг. В 2003 году это два самолёта Boeing 737-300 английской лизинговой компании Astraeus Airlines. В 2005 году Iceland Express меняет лизинговую компанию на JetX Airlines и берёт у них два MD-82. В 2006 году Hello Airways предоставляет Iceland Express четыре MD-90[1].
К 2008 году в Исландии случился кризис и материнская компания Northern Travel Holdings стала близка к банкротству. Её владельцы удержались, объединившись с другой исландской компанией Fons, к которой в результате перешла и Iceland Express. Однако, к концу года у Fons тоже возникли проблемы и авиакомпанию Iceland Express получила связанная с Fons компания Eignarhaldsfelagid Fengur, которая до этого также приобрела Astraeus Airlines[1].
После этих событий Iceland Express вернулась к лизингу самолётов от Astraeus, так как теперь обе компании принадлежали одной материнской компании — в 2009 году Iceland Express снова арендовала Boeing 757-200 у Astraeus в дополнение к своим двум Boeing 737-700. С новыми самолётами исландская авиакомпания начала полеты через атлантику в Виннипег и Ньюарк[1][4].
В конце 2011 года Iceland Express столкнулась со сложностями — Astraeus обанкротился, весь флот Iceland Express был остановлен, и десятки рейсов были отменены, в том числе новые в такие города США как Орландо, Чикаго, Майами и Белфаст. В конце концов Iceland Express нашла новую лизинговую компанию CSA Czech Holiday, которая предоставила ей в аренду два Airbus A320[5]. Уменьшение размера флота привело к тому, что Iceland Express пришлось уменьшить свою маршрутную сеть, отказавшись от всех рейсов в Северную Америку, а также большей части своих европейских маршрутов[1].
В 2012 году авиакомпания с трудом получала прибыль, столкнувшись с конкуренцией с Icelandair, новым исландским перевозчиком WOW Air, а также другими европейскими авиакомпаниями GermanWings и EasyJet[1].
В результате, летом 2012 года Iceland Express начала переговоры с WOW Air о слиянии. Сделка между двумя исландскими перевозчиками была согласована, и 24 октября 2012 года авиакомпания Iceland Express прекратила существование, а WOW Air получила флот и направления Iceland Express[1][6][7].