Klub został założony w 1930 roku jako Sielmaszstroj Rostów nad Donem, jednak do 1950 jego drużyna nie brała udziału w poważnych turniejach pod nazwami Sielmasz Rostów nad Donem i Traktor Rostów nad Donem. Wtedy właśnie zaistniała jako Torpedo Rostów nad Donem, rozgrywając mecze w rozgrywkach o mistrzostwo Rosyjskiej FSRR. Dzięki sukcesom w tych turniejach w 1953 roku awansowała do B-klasy mistrzostw Związku Radzieckiego, gdzie w 1965 roku awansowała do drugiej grupy A-klasy. Od 1957 klub nazywał się Rostsielmasz Rostów nad Donem.
W 1991 roku, po zajęciu 4. miejsca w Pierwszej Lidze awansowała do najwyższej klasy rozgrywkowej. Za pierwszym podejściem klubowi z Rostowa nad Donem nie udało się utrzymać wśród najsilniejszych i w 1993 Rostsielmasz spadł do Pierwszej Dywizji. Jednak już po roku klub wrócił do Premier Ligi, gdzie najwyższe miejsce, szóste, zajął w 1998 roku. W 1999 został zgłoszony przez rosyjską federację do gry w Pucharze Intertoto, w którym odpadł dopiero w 3. rundzie, wyeliminowany przez Juventus F.C. W kolejnym roku, także w Pucharze Intertoto Rostsielmasz został pokonany przez AJ Auxerre.
W 2003 klub zmienił nazwę na FK Rostów. W tymże roku udało się klubowi dojść do finału Pucharu Rosji, gdzie uległ Spartakowi Moskwa. W sezonie 2004 drużyna zajęła dopiero 12. miejsce. W sezonie 2005 długo okupowała ostatnie miejsce, jednak wieść o przejęciu klubu przez firmę „Argofen” tak podziałała na graczy, że wygrali 6 z ostatnich 10 meczów i uchronili Premier Ligę dla Rostowa.
Q – runda eliminacyjna, 1/16, 1/8, 1/4, 1/2 – odpowiednia faza rozgrywek, Grupa – runda grupowa, 1r gr – pierwsza runda grupowa, 2r gr – druga runda grupowa, F – finał, R – runda, PO – play-off
k. – rzuty karne, los. – losowanie, Dogr. – dogrywka, w. – zasada bramek strzelonych na wyjeździe