Narodno predanje kazuje da je Smederevsku tvrđavu zidala Jerina, Prokleta Jerina iz narodnih pesama, inače Irina Kantakuzin, vizantijska princeza udata za Đurđa Brankovića. Legenda tvrdi da je Smederevo sazidala tako što je terala narod na kuluk, čak su i trudnice morale da nose teško kamenje, da je mladim momcima nakon provedene noći s njima odsecala glave, da je iz nje zračila nekakva demonska sila pa bi svaki put kad ustane iz trave, trava pod njom izgorela. Prema jednom mitu, Jerina se odlučila da zida Smederevo baš tu gde je sazidano zato što se guske koje bi tu sletele više odatle nisu selile, a sa mestâ koja je za gradnju birala Jerina – jesu.
Kako bilo, tek činjenice govore da je Smederevska tvrđava poslednje veliko ostvarenje srpske vojne arhitekture, da je podignuta na ušću reke Jezave u Dunav s namerom da bude prestonica zemlje, tvrđava koja će odoleti turskim napadima i utvrđeni dvor despota Đurđa Brankovića. Zidana je dugo uz velike napore, od 1428. do 1453.
Tvrđava je trougaone osnove i čine je Mali i Veliki grad. Mali je imao dvostruke bedeme ojačane sa šest kula, a štitili su ga Dunav, Jezava i rov ispunjen vodom sa treće strane. Posebna pažnja bila je posvećena kopnenoj strani, pa su tu bedemi spajali četiri kule visoke do 25 metara sa nizom topovskih otvora. Glavna kula je bila u severnom delu i imala je ulaz u visini šetne staze bedema. Pored nje je bio sporedni izlaz koji je despotu Đurđu omogućavao sigurnu odstupnicu ka Dunavu u slučaju da i Glavna kula, poslednja linija odbrane, padne u ruke neprijatelju. U središtu dvorišta Malog grada bio je bunar, a uz dunavski bedem sazidana je reprezentativna palata sa četiri velike bifore i salom na spratu. Stambeni deo dvora bio je u posebnoj kamenoj zgradi.
Iste godine kad je podignut najveći deo Velikog grada, 1439, sultan Murat II je osvojio Smederevo. „Pošto je Đurađ shvatio da njegove snage nisu dovoljne da se odupre zetu, naoruža dobro grad Smederevo, ostavivši u njemu za odbranu jednog svog sina, a sam pređe Ugrima sa svojim drugim, mlađim sinom i sa celom porodicom, vodeći sa sobom mnogo sveštenika“, zapisao je dubrovački monah i istoričar Mavro Orbin u svom Kraljevstvu Slovena. Gradnja Velikog grada je dovršena između 1444. i 1453, kada je Smederevo ponovo vraćeno despotu Đurđu. Veliki grad je imao 19 kula, masivnih i visokih preko 20 metara, i pet kapija. Kopnena strana bedema, dakle najmanje zaštićena, bila je ojačana sa 11 kula, masivnih i visokih preko 20 metara. Unutar bedema bila je zadužbina despota Đurđa, crkva posvećena Blagovestima, kasnije porušena, i još jedna manja, verovatno dvorska crkva koja je kasnije pretvorena u džamiju. Za vreme despota Đurđa i njegovog sina Lazara tu je radila kovnica novca. Pored lava koji korača, heraldičkog simbola porodice Branković, na novcu se u više različitih varijanti javlja i natpis koji je označavao ime grada Smedereva.
Turci su napustili Smederevo 1867. godine i tvrđava je do kraja XIX veka bila dobro očuvana. Međutim, teško je stradala u Prvom i Drugom svetskom ratu, a naročito 1941. godine kada je eksplodirao magacin municije smešten u tvrđavi. Krajem prošlog veka obnovljen je značajan deo arhitektonskog kompleksa: restaurirani su objekti Malog grada, gradski bedemi i spoljašnji odbrambeni zid, rekonstruisana je kula na uglu Jezavskog i Varoškog bedema, i do danas su urađena obimna arheološka istraživanja. Najnovija su počela pre tri godine, kao i radovi na izradi vodoodbrambenog sistema od visokog vodostaja Dunava. Paralelno sa ovim radovima izgrađen je i novi drveni most ispred Malog grada i sanirane su drvene stepenice u južnoj kuli Malog grada.
Pa ipak, prostor Smederevske tvrđave koristi se povremeno, kao poluuređena, parkovska površina, i u prigodnim prilikama – za sajamske potrebe tokom Smederevske jeseni. U planu je, naravno, sveobuhvatna obnova, koja bi omogućila adekvatno korišćenje Smederevske tvrđave. Možda će ta planirana obnova otkriti i da li ima istine u legendama o Jerininom blagu zakopanom u lagumima ispod Smedereva.