Pilsēta nosaukta Krievijas pilsoņu kara Sarkanās armijas komandiera Semjona Budjonnija vārdā.
- 1799. gads — ar Pāvila I dekrētu apdzīvotā vieta saņēma pilsētas statusu un nosaukumu Svjatojkresta (Святой Крест — ‘Svētais krusts’), bet vienlaikus kādu laiku turpināja lietot senāko armēņu nosaukumu Karabagli.
- 1921. gads — 28. decembrī ar Krievijas PFSR NKVD valdes lēmumu pilsēta tika pārdēvēta par Prikumsku (Прикумск).
- 1935. gads — ar PSRS Centrālās izpildkomitejas 29. aprīļa dekrētu Prikumska tika pārdēvēta par Budjonnovsku.
- 1957. gads — 14. novembrī saistībā ar dekrēta izdošanu par aizliegumu apdzīvotās vietas nosaukt dzīvo līderu vārdos Budjonnovskas pilsēta tika pārdēvēta par Prikumsku.
- 1973. gads — ar KPFSR Augstākās padomes Prezidija 30. novembra dekrētu Prikumskas pilsēta tika atkal pārdēvēta par Budjonnovsku.
Pilsētas pirmais nosaukums "Svjatojkresta" cēlies no Krievijas Svētā Krusta cietokšņa, kuru Terekas lejtecē 1722. gadā dibināja Pēteris I un kurā mita no Terekas pilsētas pārceltie kazaki. 1736. gadā Svētā Krusta cietoksnis tika pamests. Svētā Krusta cietokšņa nosaukums savukārt radies no šeit kādreiz pastāvējušās grieķu kolonijas Stavropoles (tulkojumā — ‘krusta pilsēta’).