A Air Scotland foi fundada em novembro de 2002 pelo empresário iraquiano Dhia Al-Ani e iniciou suas operações em 29 de março de 2003, usando duas aeronaves Boeing 757-200 operadas pela Electra Airlines, para resorts de férias espanhóis . A empresa era fornecedora de passagens da Electra Airlines até 25 de abril de 2003, quando suas aeronaves foram suspensas pela BAA plc devido a dívidas com o operador do aeroporto. Air Scotland rescindiu o acordo com a Electra e passou a operar com a Air Holland, que concordou em retomar a operação das antigas rotas da Electra. Com o fim da Air Holland, ela começou a operar sob o certificado de operador aéreo da Greece Airways, formada a partir da Electra e de propriedade do Sr. Al-Ani, embora com apenas uma aeronave 757. Todas as aeronaves antes de 2006, que operavam para a Air Scotland carregavam a fuselagem branca do operador com o desenho da bandeira da Escócia na cauda da aeronave.[carece de fontes?]
No início de outubro de 2005, o Sr. Al-Ani vendeu sua participação na companhia aérea para o H Top Hotels Group de Barcelona, Espanha. No entanto, dificuldades administrativas na transferência de propriedade da companhia aérea resultaram no aterramento da única aeronave da operadora em Palma de Maiorca devido a contas de combustível não pagas. Os passageiros ficaram presos por até 17 horas e, em um caso, policiais armados foram chamados para acalmar os passageiros irritados atrasados em Palma de Maiorca.[2] O efeito dominó na rede da companhia aérea como resultado do atraso foi considerável. Uma aeronave foi fretada da Fischer Air Polska para ajudar a acabar com o atraso, mas voltou para a Polônia, vazio depois que o piloto recusou o serviço para a Air Scotland por acreditar que eles não haviam pago. De fato, a Air Scotland transferiu dinheiro para a conta da Fischer Air Polska naquela manhã.[3]