La même année, le pays subit une grave crise politique ainsi qu'un embargo empêchant toute activité au sein de la compagnie aérienne. Après deux ans, la compagnie achète un Fokker 28Mk 400, baptisé Lovćen, durant l'été 1996. Le Modèle:Date-, le seul avion de la compagnie établit une liaison entre Belgrade et Bari (Italie). La compagnie explique ce choix par les liens unissant l'Italie au Monténégro. La compagnie décide d'acheter un nouvel avion en Modèle:Date-.
Au début de 1999, Montenegro Airlines est contrainte d'arrêter ses opérations à la suite de la guerre du Kosovo en 1999. Le Modèle:Date-, Montenegro Airlines est à nouveau autorisée à voler. Elle décide alors d'étendre de façon significative ses vols réguliers vers l'Europe avec des liaisons vers Francfort dans un premier temps, puis Istanbul, Zurich, Ljubljana, Budapest et Skopje avant la fin 1999. Débute alors une politique d'expansion de la Montenegro Airlines. Entre Modèle:Date- et Modèle:Date-, la compagnie commande deux Fokker 100 pour remplacer ses Fokker 28Mk 400. Ces deux nouveaux appareils permettent à la compagnie de devenir une compagnie moderne. La compagnie achète deux appareils supplémentaires entre 2002 et début 2003.
Parallèlement, Montenegro Airlines devient membre de l'IATA en Modèle:Date- et adopte le système de réservation Amadeus System User permettant des réservations plus simple pour les usagers, où qu'ils habitent dans le monde.
.jpg){kind=link}
_(2).jpg){kind=link}