В 1991 году руководитель предприятия «Дагнефтепродукт» Магомед-Султан Магомедов и бывший игрок махачкалинского «Динамо» Александр Маркаров решили учредить футбольный клуб. В том же году команда приняла участие в чемпионате Дагестана. Выиграв 16 из 20 календарных матчей и ни разу не проиграв, «Анжи» стал чемпионом республики.
Почин дал повод для дальнейшего развития клуба. Следующий сезон после распада чемпионата СССР «Анжи» начал в зоне «Юг» второй лиги чемпионата России, где руководимый Махачем Керимовым финишировал на пятом месте. В том году один из основателей клуба Александр Маркаров после девятилетнего перерыва решил вернуться на поле и выглядел на нем более чем убедительно. В 13 матчах за «Анжи» лучший голеадор второй лиги чемпионата СССР всех времен смог забить 11. Любопытно, что в том сезоне вместе с Александром Ашотовичем на поле выходил его сын Михаил, впоследствии еще на протяжении нескольких сезонов выступавший за «Анжи».
В сезоне-1993 руководство клуба на пост главного тренера пригласило Владимира Петрова, при этом поставив конкретную цель — выход в первый дивизион. Команда закончила сезон на первом месте, но в связи с реорганизацией российского первенства «Анжи» остался во втором дивизионе.
В 1994 году клуб познакомился с новым наставником. На эту роль в Махачкалу позвали Ахмеда Алескерова, который решил сделать в городе новую команду. Однако по ходу сезона азербайджанский тренер покинул Дагестан, а «Анжи» закончил год с другим рулевым — Вячеславом Легким — на десятом месте.
Перед началом сезона-95 у команды появился новый наставник. Им стал Рафаэль Сафаров, воспитавший таких известных игроков, как чемпионы России Михаил Куприянов и Нарвик Сирхаев, а также капитан «Маккаби» (Петах-Тиква) Мурад Магомедов. Впрочем, вскоре Сафаров был уволен, и вакантный пост занял Александр Маркаров.
Именно в 1995 году команда получила своеобразный толчок, позволивший ей выйти затем в первую лигу. «Анжи» всегда считался кубковой командой. Дойдя до стадии 1/16 финала Кубка страны, махачкалинцы встретились с будущим чемпионом России — владикавказским клубом «Спартак-Алания». Никто даже и предположить не мог, что Валерий Газзаев со своей дружиной в Каспийске потерпит поражение (в том году «Анжи» принимал гостей на каспийском стадионе «Труд»). Сначала все складывалось в пользу «Спартака-Алании». Анатолий Канищев забил мяч в ворота голкипера «Анжи» Андрея Мананникова в середине второго тайма, и гости уже помышляли о победе. Но на 88-й минуте Алиер Ашурмамадов провел ответный мяч, а уже в дополнительное время Михаил Маркаров забил второй мяч и принес махачкалинской команде сенсационную победу.
В следующей стадии Кубка «Анжи» в гостях разгромил сочинскую «Жемчужину» со счетом 3:0. Но в четвертьфинале махачкалинцев остановило московское «Динамо».
Творцом этих ярких кубковых побед «Анжи» стал главный тренер команды на тот момент Александр Маркаров.
В 1996 году руководство «Анжи» пригласило в клуб легендарного тренера Эдуарда Малофеева, который за один сезон подарил дагестанским болельщикам долгожданный выход в первую лигу. Состав команды практически на 80 процентов состоял из местных воспитанников. Лучшим бомбардиром зоны в очередной раз стал ныне покойный Ибрагим Гасанбеков. Кстати, футболку с одиннадцатым номером, который принадлежал Гасанбекову, после его гибели в июле 1999 года никто не надевает. Этот номер навсегда закреплен за любимцем махачкалинской публики — Ибрашкой, как его любили называть и партнеры по команде, и болельщики.
1997 и 1998 годы ушли у «Анжи» на знакомство с первой лигой. А в 1999 году клуб поставил новую для себя задачу — выйти в высший эшелон российского футбола. Руководить командой был призван выходец из Дагестана Гаджи Гаджиев, который входил в тренерский штаб олимпийской сборной СССР, выигравшей Игры-1988 в Сеуле. Новый наставник «Анжи» почти полностью обновил команду, пригласив в нее малоизвестных и списанных игроков. С этим «продуктом» опытный наставник, к удивлению футбольной общественности, вывел команду в высшую лигу. Вплоть до последних туров Гаджи Муслимович не говорил, что перед «Анжи» стоит высокая цель. Махачкалинский клуб, обыграв в решающем матче саратовский «Сокол» со счетом 1:0, обеспечил себе первое место путевку в элиту.
Опять же на удивление всех Гаджиев не стал радикально обновлять состав после повышения команды в классе, а полностью его сохранил, пригласив лишь одного футболиста — македонского легионера Небойшу Стойковича, который с первых же туров закрепился в основе. «Анжи» тех времен был настоящей машиной. Дерзкий новичок ничем не уступал более именитым и опытным соперникам. Лишь раз команда проиграла в Махачкале — московскому «Спартаку» со счетом 0:2. Весь сезон находясь вверху турнирной таблицы, «Анжи» вполне мог завоевать бронзовые медали. В заключительном туре дагестанская команда встречалась в Москве с «Торпедо». Махачкалинцев устраивал ничейный итог. Все к нему и шло. Вплоть до последних секунд счет был 1:1. И тут свое слово сказал главный арбитр матча Юрий Ключников, который на последней добавленной минуте назначил сомнительный пенальти в ворота «Анжи». Так команда Гаджиева распрощалась с надеждами на третье место. Но, как бы то ни было, махачкалинцы завоевали право выступать в Кубке УЕФА.
Но и здесь клуб постигла неудача. Руководство «Глазго Рейнджерс» отказалось играть в Махачкале, и УЕФА в этой ситуации принял сторону шотландского клуба. В итоге соперники для определения победителя противостояния сыграли один матч вместо двух — на нейтральном поле в Варшаве. В нем «Анжи» под руководством Александра Маркарова потерпел досадное поражение со счетом 0:1, пропустив в концовке игры. Но еще до этого махачкалинский клуб постигла обидная неудача. В финале Кубка России с московским «Локомотивом» дагестанская команда в серии послематчевых пенальти уступила железнодорожникам. Так была упущена реальнейшая возможность получить первый в истории клуба трофей.
В 2002 году «Анжи», крайне неудачно проведя сезон, вылетел в первый дивизион. С 2003 года клуб всякий раз ставил задачу возвращения в элиту. Однако в силу различных причин махачкалинскому клубу до определенных пор не удавалось достичь этой цели. Лишь в 2009 году команда под руководством Омари Тетрадзе смогла занять первое место и вернуться в высший эшелон российского футбола.
После стартового матча следующего сезона в премьер-лиге с нальчикским «Спартаком» Тетрадзе покинул команду, а пост главного тренера занял Гаджи Гаджиев. Команда из-за кадровых проблем по ходу чемпионата не смогла подняться на высокое место и финишировала одиннадцатой.
Зимой 2011 года владельцем «Анжи» стал Сулейман Керимов, и клуб начал стремительно развиваться по всем направлениям. Другими словами, началась новая история «Анжи». Первым звездным новичком команды стал знаменитый бразилец Роберто Карлос. Позднее в команде появились Самюэль Это’О и Лассана Диарра, Юрий Жирков и Владимир Габулов, Ласина Траоре и Виллиан и другие новички.
Главным тренером был назначен авторитетный голландский специалист Гус Хиддинк. А клуб начал работать совершенно на ином, более высоком уровне, поставив перед собой серьезные задачи в российских и международных турнирах.
Сезон-2012/2013 «Анжи» завершил на рекордном для себя третьем месте, завоевав впервые в истории дагестанских команда бронзовые медали чемпионата страны. Кроме того, команда добралась до финала Кубка России, где уступила ЦСКА, а также пробилась в 1/8 финала Лиги Европы.
В начале сезона-2013/2014 вектор развития клуба сменился, и «Анжи» расстался с рядом звездных игроков, а также с зарубежными наставниками: сначала с Хиддинком, затем – с его помощником Рене Меленстеном, возглавлявшим «Анжи» считанное количество туров. В итоге же руководить командой в новых условиях было доверено Гаджи Гаджиеву, в тренерской карьере которого «Анжи» занимал особое место. Масштабная перестройка отразилась на выступлении махачкалинцев в чемпионате. «Анжи» не удалось набрать достаточное количество очков, чтобы избежать вылета.