Klub je osnovan 1920. godine u Nikšiću, Crnoj Gori, tada još za vrijeme ujedinjene velike Kraljevine Jugoslavije. Prvi naziv kluba bio je „Obilić”, kasnije od 1927. godine mijenja ime u Radnički sportski klub „Hajduk” i malo prije II. svjetskog rata u "Hercegovac".[1] 1945. godine, po ideji bivšeg fudbalera 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 je održana u zgradi „Kosovka djevoka", a istom je presjedavao narodni heroj Radoje Dakić-Brko. Klub je uz podgoričkuBudućnost klub s najvećim ugledom i velikom tradicijom. U suverenoj crnogorskoj ligi igraju od njenog osnutka 2006. godine. Najbolje rezultate postižu u sezoni 2008./09. kada osvajaju treće mjesto i plasman u pretkolo Europske lige.
