FK Čelik was established in 1957 after Nikšić-based club FK Javorak went bankrupt. While Čelik was not the official successor of Javorak, the initiative to create a club was taken by former Javorak player Savo Pejović. Eventually, a potential leader was found in Marko Orović who had a long history of business in football within Nikšić. The name "Čelik" was given in memory of Petar Saveljić, who had worked at the local steel mill before playing football with Savo Pejović.
In their first season, Čelik played in the Titogradski podsavez - South, which was fourth level in former SFR Yugoslavia. Very soon, Čelik became regular participant of Montenegrin Republic Football League (third level). First biggest success for Čelik came at the 1961, when the club from Nikšić won the Montenegrin Cup. During the '80s, Čelik became one of the most successful clubs in Montenegrin Republic Football League, but their first appearances in Yugoslav Second League came during the 90's. At the August 2012, Čelik played their first match at the First Football League.