Fu fondata il 24 ottobre 1994 dal governo del Montenegro ma il primo aereo, un Fokker F28-4000, fu comprato solo nell'autunno del 1996 e il primo volo fu effettuato il 7 maggio 1997 tra Podgorica e Bari.
Dall'inizio del 1999 fino al 23 ottobre 1999 furono vietati i voli della compagnia sull'Europa a causa dei bombardamenti NATO. Nel 2000 la compagnia si unì alla International Air Transport Association e le fu consegnato il primo velivolo di proprietà, un Fokker F100. Montenegro Airlines ha trasportato il suo milionesimo passeggero il 2 luglio 2004; lo stesso anno fu raggiunto il record di 370.000 passeggeri trasportati.
Il 24 dicembre 2020 il governo montenegrino ha annunciato la liquidazione e la conseguente chiusura della compagnia a causa di difficoltà finanziarie e ha annunciato l'intenzione di costituire un nuovo vettore aereo prima dell'inizio della stagione estiva del 2021.[2] L'ultimo volo è stato operato la sera del 25 dicembre tra Belgrado e Podgorica.[3]
Flotta
Al momento della chiusura la flotta di Montenegro Airlines era composta dai seguenti aeromobili:[4]
Il 25 gennaio 2005 un Fokker F100 ha subito il collasso del carrello anteriore dopo essere uscito di pista dopo essere atterrato a Podgorica in condizioni nevose causando il ferimento dei due piloti e di due passeggeri.[6]
Il 7 gennaio 2008 a Podgorica, durante un'ispezione di routine su un Fokker F100, è stato scoperto un foro di proiettile sui piani orizzontali probabilmente causato da un colpo sparato durante i festeggiamenti dell'Epifania e del Natale ortodosso; nessuno è rimasto ferito.[7]
L'11 novembre 2018 uno dei turbofanRolls-Royce Tay del Fokker F100 4O-AOP ha subito un cedimento strutturale nella camera di combustione causando lo spillamento di aria ad elevate temperature nel condotto di bypass producendo letture errate sulla strumentazione di cabina relativa ai motori ma entro i limiti operativi; l'aereo è atterrato in sicurezza a Podgorica.[8]