Компания была основана в ноябре 2002 года бизнесменом иракского происхождения Диа Аль-Ани и начала осуществлять авиаперевозки на испанские средиземноморские курорты 29 марта 2003 года, используя 2 самолёта Boeing 757—200 авиакомпании Electra Airlines. Air Scotland продавала билеты на рейсы Electra Airlines до 25 апреля 2003 года, когда компания BAA plc, крупнейший в Великобритании владелец и оператор аэропортов, фактически заморозила деятельность Electra Airlines, арестовав её лайнеры за долги. Air Scotland аннулировала своё соглашение с Electra Airlines и вскоре заключила аналогичный договор с авиакомпанией Air Holland, согласившейся продолжить перевозки на бывших маршрутах Electra Airlines.
Сотрудничество с Air Holland было также непродолжительным. После прекращения этой авиакомпанией своей деятельности в марте 2004 года Air Scotland начала использовать сертификат воздушного оператора, выданный греческими властями компании Greece Airways, ставшей преемницей Electra Airlines после её банкротства. Greece Airways также принадлежала г-ну Аль-Ани, однако имела в своём распоряжении уже только один Boeing 757—200.
В начале 2005 Диа Аль-Ани продал Air Scotland испанскому гостиничному оператору H Top Hotels Group. Административные сложности, связанные со сменой собственника авиакомпании, привели к аресту единственного самолёта Air Scotland в аэропорту Пальма-де-Мальорки за отказ оплатить счета за авиационное топливо. Вскоре Air Scotland была вынуждена расстаться со своим «Боингом» и взять в лизинг «Аэробус А320».
Air Scotland имела в своём распоряжении всего один самолёт A320-211, базировавшийся в Глазго. У компании были планы по приобретению второго аналогичного лайнера, который должен был базироваться в Жироне.
