The club was founded in 1921 with the name NTK (Novosadski Trgovački Klub, Novi Sad Commercial Club), and played in the regional leagues. In 1923, the won the local Novi Sad football league. In 1954, FK Eđšeg (named Jedinstvo) and FK Radnički (NTK) were merged into one club, renamed into RFK Novi Sad (Radnički Fudbalski Klub Novi Sad). The club moved to the stadium which was formerly of Jedinstvo and the yellow and blue colors were inspired by the pre-war club NAK Novi Sad.
Since then, the club started improving in the competition, and in 1961 they earned promotion to the Yugoslav First League. They played 3 seasons in the national highest level, with best Yugoslav teams coming to play to Detelinara Stadium. In their first top flight season they experienced difficulties and finished in 10th place out of 12 teams, avoiding relegation by only one spot. However in 1962–63 their performance was much stronger and they finished in 8th in an expanded 14 teams competition in front of traditionally stronger teams such as Hajduk Split or their main city rivals, Vojvodina. However in 1963-64 they finished 13th and by only one point they did not manage to avoid relegation. The competitiveness that season was so tough that at the end only 4 points separated the 7th-placed Vojvodina from the bottom team, 14th, FK Vardar. Ever since, RFK Novi Sad never managed again to play in the national top flight, playing mostly in the Yugoslav Second League during Yugoslav period.
After the dissolution of SFR Yugoslavia in 1991, RFK Novi Sad became the only club to play in 14 consecutive editions of the Second League of FR Yugoslavia. In 2006, they were relegated, however, after only one season, they were back to the, now renamed, Serbian First League. In 2011, the club celebrated its 90th birthday. In 2012, the club has changed its name in FK Novi Sad.