אנז'י מחצ'קלה נוסדה בשנת 1991 על ידי מאגומד-סולטאן מאגומדוב, שהמשיך לכהן כנשיא הקבוצה עד שנת 2011. כבר בשנה הראשונה זכתה הקבוצה באליפות דאגסטן והעפילה לליגה הרוסית השנייה. ב-1996 מונה אדוארד מאלופייב למאמן, מי שאימן בעבר את דינמו מינסק והביא אותה לאליפות ברית המועצות ב-1982, ב-1996 הוא הביא את הקבוצה עד לרבע גמר גביע רוסיה אך הפסידה לדינמו מוסקבה. ב-1999 הוא הביא את הקבוצה לזכייה בליגה הרוסית הראשונה והעפלה לליגה הרוסית הבכירה.
בעונת הבכורה שלה בליגת העל הרוסית, בשנת 2000, אנז'י סיימה במקום הרביעי והבטיחה את השתתפותה לראשונה במפעל האירופי בגביע אופ"א. בשנת 2001 אנז'י הגיעה עד לגמר הגביע הרוסי, אך הפסידה ללוקומוטיב מוסקבה. באותה שנה הקבוצה שיחקה מול גלאזגו ריינג'רס בגביע אופ"א. תחילה סירבה ריינג'רס לשחק בדאגסטן בשל המצב הביטחוני והמשחק הועבר לשטח נייטרלי. המשחק נערך בוורשה, אך לבסוף הודחה הקבוצה מהטורניר האירופי.
בשנת 2002 הקבוצה ירדה ליגה אל הליגה הרוסית הראשונה והחליפה 3 מאמנים בזה אחר זה (לאוניד טקאצ'נקו, מירון מארקביץ' וגאג'י גאג'ייב).
בשבע השנים הבאות (2003–2009) הקבוצה העבירה בליגה הרוסית הראשונה ועד 2007 החליפה הקבוצה 9 מאמנים. ב-2007, מונה אומרי טטראדזה למאמן והוא שהוביל את הקבוצה בעונת 2008/09 לזכייה באליפות הליגה הרוסית הראשונה ועברה לשחק בעונת 2010 בליגה הרוסית הבכירה, אחרי בצורת של מספר שנים.
בתחילת עונת 2010 הגיש טטראדזה את התפטרותו מתפקיד המאמן, זאת לאחר שוויון מול ספרטק נלצ'יק. במקומו מינה הבעלים מאגומד-סולטאן מאגומדוב את גאג'י גאג'ייב, מאמן העבר של הקבוצה, שמונה שוב למאמן ופוטר בספטמבר 2011 בשל חוסר יכולת להציב את הקבוצה בראש טבלת הליגה[1].
בינואר 2011 הושלמה רכישת 100% ממניות הקבוצה על ידי המיליארדר הרוסי ממוצא דאגסטני, סוליימאן קרימוב, שהבטיח להשקיע בכדורגל הדאגסטני רבות, והודיע כי בכוונתו להשקיע כ-50 מיליון דולר מדי שנה. נוסף לזה הוא הבטיח להקדיש 200 מיליון דולר לבניית תשתית ספורט רחבה עבור הכדורגל בדאגסטן, תוך הקמת אצטדיון מודרני שיעמוד בקריטריונים של אופ"א. חלון ההעברות של חורף 2011 היה לעונה היסטורית כאשר בקבוצה חתמו שחקני נבחרת ברזיל רוברטו קרלוס, ז'וסילי דה סילבה ודייגו טארדלי. אחר כך חתם בקבוצה שאמיל לחיאלוב, קפטן טרק גרוזני לשעבר, ולפני סגירת חלון ההעברות במרץ חתמו גם מבארק בוסופה, מקבוצת הכדורגל אנדרלכט ויורי ז'ירקוב, שחקן נבחרת רוסיה שנרכש מידי צ'לסי. באוגוסט 2011 אנז'י החתימה לשלוש שנים את סמואל אטו, שהפך לשחקן הכדורגל שמרוויח הכי הרבה לעונה בודדת; 20 מיליון יורו לעונה[2]. בפברואר 2011 הוחתם חוס הידינק כמאמן הקבוצה, למשך שנה וחצי. ביולי 2013 התפטר הידינק מאימון הקבוצה, ולאימון הקבוצה מונה עוזרו, רנה מיולנסטיין. מיולנסטיין פוטר לאחר 16 ימים בתפקיד, ובמקומו מונה גדז'י גדז'ייב. בהמשך הופחת תקציב הקבוצה ל-42 מיליון יורו, ושוחררו שחקנים בכירים. הפחתת התקציב הביאה גם לפיחות ביכולות של הקבוצה ובעונת 2013/14 התדרדרה הקבוצה עד למקום האחרון בליגה הרוסית, אם כי הקבוצה העפילה לשמינית גמר הליגה האירופית, לאחר שגברה על גנק הבלגית. הקבוצה סיימה את העונה במקום ה-16 והאחרון והודחה לליגת המשנה הרוסית. בתום עונת 2014/15 הקבוצה סיימה במקום השני והעפילה בחזרה לליגה הבכירה.
בדצמבר 2016סוליימאן קרימוב מכר את הקבוצה לידי איש העסקים אוסמן קאדייב. בעונת 2017/2018 הקבוצה התמודדה במשחקי מבחן נגד יניסיי והפסידה והייתה אמורה לנשור חזרה לליגת הכדורגל הלאומית של רוסיה. אך בשל פירוקה של אמקאר פרם מליגת העל, היא הוחזרה לליגה הבכירה. ברם, במהלך עונת 2018/2019 הקבוצה נתקלה בקשיים כלכליים רבים, בעקבות הקפאת חשבונותיו של אוסמן קאדייב והסנקציות הכלכליות שהטילה ארצות הברית על אוליגרכים רוסים בעקבות החשד למעורבות הרוסית בבחירות 2016.[3] בסיום אותה עונה ירדה לליגת הכדורגל המקצוענית, כשבאמתחתה השיא השלילי הגרוע ביותר במאזן הבקעת שערים: 13 בסך הכל.[4] בקיץ 2022, הקבוצה פורקה בעקבות פשיטת רגל של בעליה, אוסמן קאדייב.
לאנז'י יש יריבות חזקה עם אחמט גרוזני מצ'צ'ניה הסמוכה. המשחקים ביניהן תמיד משכו קהל רב לאצטדיונים בעיקר בשל העובדה ששתי הקבוצות מייצגות את שני אזורי העימות הנפיצים ביותר בדרום רוסיה. שתיהן טוענות לבכורה בזירה הלאומית ברוסיה והיריבות התחזקה לאחר שטרק גרוזני העפילה לליגת העל הרוסית בכדורגל בעונת 2005. משנת 2010 ועד 2019 אנז'י חזרה להתמודד בליגה הבכירה (אחרי שהתמודדה בה בעונת 2000) והמשחקים ביניהן היוו ליריבות מתוחה במחוזות הבית, דאגסטן וצ'צ'ניה.
