В 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. Но еще до этого «Анжи» вновь постигла неудача. В финале Кубка России с московским «Локомотивом» дагестанская команда в серии одиннадцатиметровых ударов проиграла железнодорожникам. Так был упущен очередной трофей.