Klub je osnovan 1920. godine u Nikšiću, tada dijelom Kraljevine Srba, Hrvata i Slovenaca. Prvi naziv kluba bio je Obilić. Godine 1927. mijenja ime u Radnički sportski klub Hajduk. Prije Drugog svjetskog rata mijenja ime u Hercegovac.[1] Godine 1945. na ideju bivšeg nogometaša Steva Matovića klub dobiva sadašnji naziv u čast poginulim borcima u Bitci na Sutjesci među kojima su bili i igrači kluba. Osnivačka skupština FK Sutjeske održana je u zgradi „Kosovka djevoka", a istom je presjedavao narodni herojRadoje Dakić. U suverenoj crnogorskoj ligi igraju od njenog osnutka 2006. godine.