De club werd in 1924 opgericht als Rodopski Sokol, maar nam later de naam Arda aan naar de gelijknamige rivier die door de stad stroomt. Tussen 1945 en 1957 speelde de club als Minjor Kardzjali. In 1956 eindigde de club op een tweede plaats in de tweede klasse. De club speelde meestal in de tweede en derde klasse, maar werd wegens financiële problemen ontbonden in 2013.
In 2015 werd de club heropgericht en begon opnieuw in de vierde klasse. Na één seizoen promoveerde de club naar de Treta Liga. In 2017 kreeg de club nieuwe investeerders en de club slaagde erin te promoveren naar de Vtora Liga. In 2019 promoveerde de club naar de hoogste klasse.
De 4e plaats in het seizoen 2020/21 was voor de club genoeg om Europees te mogen debuteren. Nummer 3 CSKA Sofia won ook de Bulgaarse beker waardoor Arda die kwalificatieplaats mocht innemen.