De club werd in 1927 opgericht. Nadat Montenegro zich in 2006 afscheurde van Servië werd er een eigen competitie opgericht. FK Zeta, Budućnost Podgorica en Jedinstvo Bijelo Polje speelden in de hoogste klasse van Servië en Montenegro, de overige clubs werden gerekruteerd uit lagere klassen. Sutjeska speelde wel al zeven seizoenen in de hoogste klasse van Servië en Montenegro. In 2013 en 2014 werd de club landskampioen onder leiding van coach Dragan Radojičić. In 2017 won het voor het eerst de beker. In de finale werd FK Grbalj met 1-0 verslagen.
De navolgende voetballers kwamen als speler van FK Sutjeska Nikšić uit voor een vertegenwoordigend Europees A-elftal. Tot op heden[3] is Vladimir Jovović degene met de meeste interlands achter zijn naam. Hij kwam als speler van FK Sutjeska Nikšić in totaal vijf keer uit voor het Montenegrijnse nationale elftal.