First seasons of their existence, Čelik spent in the lowest-tier competition ("Titogradski podsavez"). First successes for Čelik came with the beginning of sixties. On 1961, as a member of Fourth League, the team won the Montenegrin Republic Cup. The same year, Čelik debuted in the Montenegrin Republic League (third level). Significant success came on season 1967-68. As a runner-up of Republic League, Čelik gained its first-ever promotion to the Yugoslav Second League. In that competition, Čelik played its first official games against Nikšić strongest-side FK Sutjeska and notable Montenegrin team FK Budućnost, but they were relegated, with scores of four wins, six draws and 20 defeats.