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