Клуб је основан 20. априла 1920. године, као секција Спортског друштва Раднички, основаног од младих радника (претежно грађевинара) и Независних синдиката. Пре је био познат као Раднички Нови Београд, све док му спонзор није постао нафтна компанија Југопетрол. Играо је у Првој савезној лиги Југославије девет сезона и то од сезоне 1953/54. до 1960/61, a последњи пут у сезони 1965/66. Највећи успех у својој историји клуб је остварио освајањем трећег места у Првој лиги Југославије у сезонама 1955/56. и 1957/58, четвртог места у сезони 1958/59, као и учешћем у финалу Купа Маршала Тита против београдског Партизана у сезони 1956/57. То финале је остало у сећању љубитеља фудбала по преокрету у резултату. Наиме Раднички је после вођства од 3:0 у првом полувремену, изгубио утакмицу са 3:5!
Након распада СФР Југославије, од сезоне 1992/93. до 1995/96. је играо у Првој лиги СР Југославије и 2004/05. у Првој лиги Србије и Црне Горе. После те сезоне испали су у трећу лигу због финансијских проблема, где су играли до сезоне 2008/09. када је клуб у Српској лиги Београд заузео последње 16. место и испао у нижи ранг, Београдску зону.