Klubo ištakos siekia 1914 m. 1937 m. tapo Juodkalnijos čempionais. Jugoslavijos laikotarpiu priklausė šios šalies futbolo sistemai. Atkūrus Juodkalnijos nepriklausomybę (2006 m.), klubas rungtyniavo žemesniuose divizionuose. Vėliau paeto į Antrą lygą. 2021–2022 metų sezone „Arsenalas“ Antroje lygoje iškovojo antrą vietą. Po sezono buvo perkelti į aukščiausią lygą.
2022–2023 m. sezone Pirmoje lygoje užėmė trečią vietą. 2022–2023 m. Juodkalnijos futbolo taurės turnyre pasiekė finalą. 2023 m. ppgegužės 29]] d. finalo rungtynėse
po pagrindinio laiko buvo lygus rezultatas (1-1). Sutjeska nugalėjo varžovus tik baudinių serijos metu ir iškovojo šalies futbolo taurę.[1][2]