Команда была образована как одна из двух секций спортивного клуба ПЗЛ «Мелец» в 1939 году. Первые матчи проводились с местными командами. Но с началом Второй мировой войны клуб прекратил существование. В 1976 году команда играла в финале Кубка Польши, но уступила клубу «Слёнск» (0:2). Клуб пять раз принимал участие в еврокубках и наибольшего успеха добился в Кубке УЕФА сезона 1975/76, где в 1/4 финала по сумме двух матчей уступил немецкому «Гамбургу» (1:1 и 0:1). Лучшим бомбардиром клуба является знаменитый Гжегош Лято, который выступал за «Сталь» на протяжении 18 сезонов и забил в общей сложности за клуб 138 мячей. Домашние матчи команда проводит на стадионе «Сталь», вмещающем 25 000 зрителей (после реконструкции 30 000).