В 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 вектор развития клуба сменился, и «Анжи» расстался с рядом звездных игроков, а также с зарубежными наставниками: сначала с Хиддинком, затем – с его помощником Рене Меленстеном, возглавлявшим «Анжи» считанное количество туров. В итоге же руководить командой в новых условиях было доверено Гаджи Гаджиеву, в тренерской карьере которого «Анжи» занимал особое место. Масштабная перестройка отразилась на выступлении махачкалинцев в чемпионате. «Анжи» не удалось набрать достаточное количество очков, чтобы избежать вылета.

В прошлом сезоне в ФНЛ команда не сразу вышла в лидеры. Потребовалось некоторое время, чтобы значительно обновленный коллектив нашел свою игру. Это произошло уже ближе к концу первой части сезона, и рывок у подопечных Сергея Ташуева получился впечатляющий. Команда выиграла восемь из девяти игр перед уходом на зимние каникулы и не только вышла на первое место, но и прилично оторвалась от конкурентов. Две подряд победы весной, после возобновления первенства, казалось, обеспечили «Анжи» спокойную жизнь на финише. Однако затем команда несколько сбавила обороты, стабильно набирая очки дома, но раз за разом допуская осечки в гостевых матчах. Что, однако, не помешало «орлам» за тур до окончания первенства гарантировать себе выход в Премьер-Лигу со второго места.

К сезону в элитном дивизионе «Анжи» подошел под руководством нового главного тренера – Юрия Семина, одного из самых авторитетных отечественных специалистов. Два нелогичных, не по игре, домашних поражения и минимальное от ЦСКА на выезде в первых трех турах поставили в сложное положение команду, в которой немало дебютантов Премьер-Лиги. Даже гостевая победа над московским «Спартаком» в 7-м туре не стала для «Анжи» психологическим трамплином, который помог бы выбраться из нижней части турнирной таблицы. После ничьей в родных стенах с «Уфой» в 10-м туре Семин и клуб приняли решение расстаться по обоюдному согласию, и команду возглавил рекордсмен «Анжи» по количеству проведенных матчей Руслан Агаларов, ранее на протяжении четырех сезонов руководивший «молодежкой» клуба.