Klub je osnovan 1921. godine pod nazivom NTK (Novosadski Trgovački Klub), te se do Drugog svjetskog rata uglavnom natjecao u prvenstvima Novosadskog nogometnog podsaveza. Klub se tada često i nazivao Trgovački, te je bio dio športskog društva Trgovačka Omladina.
1948. godine tvrtka "Stobeks" reaktivira NTK pod nazivom Trgovački, koji taj naziv nosi do 1954. godine kada mijenja naziv u FK Novi Sad. 1956. godine komunistička vlast gasi klub "Eđšeg" (tada NSK) te se spaja s Novim Sadom, te mu predaje svoju imovinu.
1961. godine, Novi Sad postaje članom Prve savezne lige, u kojoj nastupa tri sezone, a potom sljedećih desetljeća je uglavnom u drugoligaškom ili trećeligaškom natjecanju.
1966. godine se FK Novi Sad spaja s klubom Radnički i nastaje RFK Novi Sad.
2012. godine zbog gašenja Sportskog Društva "Radnički", klub vraća naziv FK Novi Sad. 2014. godine zbog financijskih problema i izbacivanja kluba u najniži rang (Gradska liga Novi Sad - šesti rang), klub donosi odluku o promjeni naziva u RFK Novi Sad 1921.