Było to około 1038 roku Książę czeski Brzetysław napadł na Śląsk, który w tym czasie należał do Królestwa Polskiego. Oddziały księcia Brzetysława zaczęły zagrażać nawet Krakowowi. W tym czasie zmarł król Polski Mieczysław II i kraj pozbawiony był władcy.

Ostatni z synów zmarłego króla - Kazimierz, jako najmłodszy przebywał w klasztorze Chegney we Francji południowej i nie miał zamiaru go opuszczać. Gdy jednak przybył doń wojewoda krakowski przedstawiając mu ciężkie położenie kraju i w imieniu narodu prosząc go o powrót do Polski i objęcie rządów, młody królewicz dał się namówić i z orszakiem rycerzy wrócił przez Niemcy i Śląsk by objąć władzę jako nowy król Polski zwany Kazimierzem Odnowicielem.

Jechał tedy Kazimierz przez Śląsk opustoszony i zabiedzony by wreszcie przeprawiwszy się przez rzekę Brynicę, zwaną wówczas Braną zauważył na rozległej polanie mnóstwo pasących się jeleni, saren, i dzikich koni, wobec czego rozkazał swemu orszakowi: - Strzelać, strzelać! - ale sfrancuziały mocno królewicz kiepsko wymawiał słowo „strzelać” przeto rycerze, giermkowie i towarzysząca mu służba (czeladź) odebrali to polecenie jako „czeladź - strzelać”. I strzelano ubijając dużo zwierzyny na dalszą drogę.

Tak miała powstać nazwa miasteczka Czeladź, która wkrótce tu powstała. Dodać należy że nazwa miasta w średniowieczu różnie była pisana. I tak, według starych zapisów zwano ją: Chelad (1225), Celezc (1238), Celaz (1242), Celad (1243), Czheladiz (1257), Zelezt (1250), Czedlez (1328), Czelacz (1468) czy Czelącz (1529).

Współcześni językoznawcy nazwę miasta Czeladzi wywodzą jednak od „czeladzi” - służby będącej na usługach możnowładcy tych ziem.