Dibināta 1736. gadā, kad Miasas upes krastā Orenburgas aizsardzībai pret baškīriemKrievijas impērijas armija uzcēla Čeļebi (Челеби) cietoksni, kura nosaukums tjurku valodā nozīmē ‘caradēls’ vai ‘izglītotais’. Jau 1744. gadā cietoksni ieņēma Jemeļjana Pugačeva karaspēks. 1787. gadā Čeļabinskai piešķīra pilsētas tiesības. 1890. gados pilsēta sāka strauji attīstīties saistībā ar Transsibīrijas maģistrāles izbūvi. 1918. gada maijā Čeļabinskā notika incidents, kurš noveda pie Čehoslovāku leģiona dumpja.
Vēl vienu impulsu pilsētas attīstībai deva Otrais pasaules karš, kad no PSRS rietumu apgabaliem šeit tika pārceltas lielas militārās rūpnīcas — kara gados Čeļabinska bija tankuT-34 un reaktīvo ieroču, t.s. katjušu ražošanas centrs.