Клуб основан 1 октября 2015 года под названием «Легион». Инициатором его создания стал известный в прошлом дагестанский футболист Шамиль Гаджиалиевич Лахиялов, который в настоящее время является президентом клуба. В своё время он стал первым дагестанцем, забивавшим в Лиге Европы в составе «Анжи».
Для Дагестана «Легион» уникален тем, что представляет собой социальный проект, позволяющий местным футболистам, играть на профессиональном уровне. Первый год своей истории «Легион» провёл в любительском статусе, став бронзовым призёром Лиги чемпионов ЮФО, выиграв Кубок Дагестана, Кубок города, чемпионат ЛФЛ Дагестана сезона – 2015/16, Лигу чемпионов Дагестана. 1 июля 2016 г. ФК «Легион» обзавёлся приставкой «Динамо». Это было связано с тем, что команда получила возможность проводить свои домашние матчи на стадионе «Динамо».
На второй год существования «Легион Динамо» прошёл лицензирование и был заявлен для участия в первенстве ПФЛ России, зона «Юг». В дебютном сезоне 2016/17 гг. «легионеры» только в заключительном туре сумели сохранить прописку в профессиональном футболе. В этом же сезоне команда во второй раз выиграла Лигу чемпионов Дагестана. В сезоне – 2017/18 коллектив Шамиля Лахиялова занял 9-е место из 17. И вновь «легионеры» стали сильнейшими в престижном республиканском турнире – Лиге чемпионов Дагестана, получив кубок на вечное хранение, как трижды подряд выигравшие турнир.
Клуб занимал следующие места в Первенстве Второй лиги России:
2018/19 – 7-е место (из 15 команд); 2019/20 – 5-е место (из 16);
2020/21 – 4-е место (из 17); 2021/22 – 7-е место (из 17);
2022/23 – 9-е место (из 13); 2023 – 6-е место (из 14).
В июле 2022 г. клуб вернул себе прежнее название. Как отметил Шамиль Лахиялов «Легион» часто называют народной командой, потому что бюджет формируется в основном из пожертвований людей, которые неравнодушны к дагестанскому футболу.
Зимнее трансферное окно значительно поменяло состав "легионеров" — 12 новых футболистов оделись в жёлто-чёрные цвета клуба. Среди них: вратари Ахмед ДАВУДОВ («Динамо-2», Махачкала); защитники Руслан КАРАВАЛЛИЕВ («Динамо», Санкт-Петербург), Артём КОЖУХАРЬ («Носта», Новотроицк), Александр ОЛЕНЁВ («Астрахань»), Шамиль ГАСАНОВ («Сурхан», Узбекистан); полузащитники Ибрагим КАТИНОВАСОВ («Сахалин», Южно-Сахалинск), Юрий УДУНЯН («Велес», Москва), Данил МАССУРЕНКО («Калуга», Калуга), Роман ПОЛКОВНИКОВ («Химки-М», Химки); нападающие Абдурахман КУРБАНАЛИЕВ («Динамо-2», Махачкала), Тимур ГАЛИМЗАНОВ («Салют», Белгород) и Давид ХОКРИШВИЛИ («Алания-2», Владикавказ).
«Легион» стартовал в сезоне с трёх побед подряд. Последовательно были обыграны «Кубань Холдинг» – 2:1, «Динамо-Ставрополь» – 3:1 и «Победа» – 1:0.
«Севастополь» и «Легион» ранее в официальных матчах не встречались.
«Легион» проводит домашние игры в Махачкале на искусственном газоне стадиона «Труд». Вместимость трибун – 5600 зрителей.