Клуб је основан 1970, а за његово оснивање најзаслужнији су Мирољуб Поповић, тадашњи директор Кадровског сектора Комбината Боривоје Јовановић, Херберт Форстер и Божидар Маровић.
Први председник и тренер Рудара је био Мирољуб Поповић - Цицко, некадашњи рукометаш и оснивач клуба. Клуб је такмичење почео од најнижег ранга, Регионалне лиге Смедерево, па је преко Друге и Прве српске лиге, стигао 1988. до Друге савезне лиге Југославије, где се такмичио до 1993.
Уз финансијску помоћ ИЕК-а „Костолац“, Рудар ИЕК Костолац у сезони 1993/94. осваја прво место у Другој савезној лиги и улази у Прву савезну Б лигу, други ранг такмичења. Рудар се након реорганизације лиге у сезони 1999/00. такмичио у Другој савезној лиги, а у наредним годинама Рудар је стигао и до Суперлиге. Потом је више сезона поново играо у другом рангу, Првој лиги, пре него што се у сезони 2010/11. као првак Прве лиге пласирао у Суперлигу Србије, где се тренутно такмичи.[2]