באפריל2000 הצטרפה החברה לארגון חברות התעופה יאט"א, ביוני אותה שנה קבלה את מטוס הפוקר 100 הראשון שלה, עד שנת 2003 רכשה החברה עוד ארבעה מטוסים מדגם זה.
בשנת 2004 הטיסה מונטנגרו איירליינס את הנוסע המיליון שלה, באותה השנה טסו בחברה כ-370,000 נוסעים.
לאחר פירוק סרביה ומונטנגרו בשנת 2006, הפסיקה החברה להפעיל טיסות מסרביה למדינות אחרות (למעט למונטנגרו).
בין המדינות החדשות לא היה חופש תנועה אווירי, וכך איבדה את אחד הקווים הרווחיים שלה ניש-ציריך. בניסיון לעקוף את האיסור, הקימה מונטנגרו איירליינס חברת תעופה נפרדת רשומה בסרביה בשם מאסטר איירוויז (Master Airways), אולם החברה החדשה לא קבלה רישיון הפעלה מממשלת סרביה.
בספטמבר2008 הזמינה מאמבראר מטוס E-195 נוסף, אם אופציה לרכישת מטוס נוסף מדגם זה.
בשנת 2009 הודיעה ממשלת מונטנגרו על הפרטת החברה. באפריל אותה השנה פורסם כי אל על מתעניינת ברכישת 30% ממניות מונטנגרו איירליינס[2], תוכנית זו לא יצאה לפועל. בשנת 2010 פורסם כי ארקיע בוחנת את האפשרות להיכנס כשותפה בחברה[3].
בדצמבר2020 הודיעה ממשלת מונטנגרו על סגירת החברה עקב ניהול כושל והפסדים במשך מספר שנים. החברה ביצעה את טיסתה האחרונה ב-26 בדצמבר.
שותפות קוד
למונטנגרו איירליינס היה הסכמי שותפות קוד עם החברות הבאות: