Narodno predanje poreklo imena Smedereva vezuje za graditelje tvrđave despota Đurđa Brankovića i njihove reči „sme i drvo“, izgovorene pod teretom mukotrpnog zidanja. Sačuvani istorijski izvori, ipak, otkrivaju drugačiju hronologiju: naziv grada zabeležen je vekovima pre nego što je između 1428. i 1430. godine podignuto monumentalno utvrđenje na Dunavu.
Prema predanju, graditelji su masivne kamene blokove prenosili iz ruke u ruku, iscrpljeni napornim i dugotrajnim zidanjem. U jednom trenutku neko od njih navodno je predložio da se za gradnju, osim kamena, upotrebi i drvo, izgovorivši reči „sme i drvo“. Te reči potom su se prenosile od graditelja do graditelja, a narod ih je vremenom povezao u „Smederevo“ i pretvorio u objašnjenje nastanka imena grada.
Reč je o živopisnom predanju, ali sačuvani izvori upućuju na znatno starije poreklo naziva. Mesto se pominje još 1019. godine u povelji vizantijskog cara Vasilija II, u odeljku posvećenom Braničevskoj eparhiji. Knez Lazar 1381. godine u povelji manastiru Ravanici navodi Smederevo kao razvijeno naselje sa stanovnicima, opštinom i baštinom.
U dokumentima nastalim izvan slovenskog prostora grad beležen je kao Semendria, naročito u latinskom, italijanskom, rumunskom i grčkom jeziku. Mađarski oblik glasio je Szendrő, a osmanski Semendire.
O poreklu imena Smedereva postoji još nekoliko pretpostavki. Prema jednoj, naziv je nastao spajanjem reči „smet“, u značenju snežnog nanosa, i stare slovenske reči „drevo“, koja označava drvo, što se povezuje sa nekadašnjim hrastovim šumama našeg kraja. Pojedina tumačenja poreklo imena dovode u vezu sa rimskim nazivom Mons Aureus, odnosno Zlatnim brdom u blizini Smedereva. Ipak, ni ta pretpostavka nije pouzdano potvrđena istorijskim izvorima.
Predanje o rečima „sme i drvo“ ostalo je kao slikovita priča o naporima graditelja tvrđave, ali ne i kao pouzdano objašnjenje porekla imena. Istorijski zapisi potvrđuju da je Smederevo pod tim nazivom postojalo znatno pre njenog podizanja, a u evropskim spisima vekovima je beleženo kao Semendria.