Основан је 1954. под именом „Млада Босна“ и клуб је своје утакмице тада играо на отвореном терену у ФИС-у. Млада Босна је већ 1955. учествовала на финалном турниру Првенства Југославије, где је заузела друго место иза Црвене звезде. Исти резултат је поновљен на финалном турниру 1956. у Сарајеву. Године 1957. Млада Босна се као победник квалификационог турнира пласирала на финални турнир првенства у Сарајеву, где је заузела треће место, а пласманом на финални турнир се квалификовала и за првенство следеће године, кад се први пут играла лига.
Од сезоне 1957/58. се играло по двоструком лига систему, а Млада Босна је ту сезону завршила на претпоследњем седмом месту. Наредна сезона 1958/59. је била далеко успешнија па је Млада Босна заузела треће место, са само бодом мање од првопласираног бањалучког Борца. Сезону 1959/60. је завршила у средини табеле, док је у сезони 1960/61. за мало измакла титула првака, пошто је Млада Босна заузела друго место иако је имала исти број бодова као првопласирани бјеловарски Партизан. Клуб се под именом Млада Босна такмичио у Првој савезној лиги све до сезоне 1969/70, а најбољи резултат из тог периода је било четврто место у сезони 1967/68.
Млада Босна 18. маја1970. мења име у „Жељезничар“,[2] а почетком седамдесетих клуб је почео своје утакмице играти у дворани КСЦ Скендерија.[3] Прве две сезоне под тим именом клуб је завршавао у доњем делу табеле Прве савезне лиге, док је први значајнији резултат било четврто место у сезони 1972/73.
Друга половина седамдесетих и почетак осамдесетих су били најуспешнији период у историји клуб. У сезони 1974/75. Жељезничар заузео друго место, наредне 1975/76. треће, а након тога је уследила слабија сезона у којој је заузео осмо место. Ипак већ у следећој сезони 1977/78. под вођством тренера Сеада Хасанефендића освојио је своју прву и једину титулу првака Југославије, завршивши сезону са бодом више од бјеловарског Партизана, који је бранио титулу из претходне сезоне.[4]Жељезничар се задржао у врху југословенског рукомета још наредне три године, па је сезону 1978/79. завршио на трећем месту, а наредне две као другопласирани. Као други у Првој савезној лиги у сезони 1980/81, Жељезничар је играо у првом издању ЕХФ купа у сезони 1981/82, где је успео да стигне до финала, али је тамо поражен од немачког Гумберсбаха са 23:14.[5]
Жељезничар је наставио са такмичењем у Првој савезној лиги и наредних година али није имао значајнијих резултата. Након распада Југославије са такмичењем је наставио прво у лиги Федерације БиХ, а након тога се повремено такмичио у Премијер лиги БиХ. Због финансијских проблема Жељезничар је у првом делу сезоне 2010/11. Премијер лиге искључен из такмичења.[6] Клуб није био активан наредних годину дана, а од сезоне 2011/12. је наставио са такмичењем у Првој лиги ФБиХ-Југ, другом рангу такмичења.[7]
