Festningen som rager opp på fjellet på Vltavas høyre bredde er omtrent hundre år eldre enn Slottet i Praha. Den skal ha blitt etablert av den legendariske fyrsten Krok. På slutten av 1000-tallet holdt fyrste Vratislav II. til her. Senere ble Vyšehrad først og fremst en festning som beskyttet Praha fra syden.
I perioden fra 1400- til 1800-tallet var Vyšehrad og omgivelsene en by med selvstyre. Den ble en del av Praha i 1883.
I anlegget finnes det Peter- og Paulkirke, kirkegård Slavín hvor flere viktige tsjekkere ligger begravet, og Martinsrotunde.
Det er noen legender knyttet til Vyšehrad. Etter en legende er det en borg som ble bygget av fyrste Krok på det bratte fjellet da han lette etter et tryggere sted for sitt sete. Da Krok døde, var det dattera hans som overtok makten. Det likte ikke mennene i riket som ikke ønsket seg at kvinner regjerte. Derfor sendte Libuše bud på hest. Budet skulle komme med den mann som hesten ville stanse ved. Og det var en Přemysl som nettopp pløyde da hesten stanset ved ham. Hermed ble mannen fjerde hersker i det tsjekkiske riket. Han fikk kallenavnet Přemysl Oráč - Pløyer.
En annen legende forteller om ridder Horymír som satt i fengsel på Vyšehrad under fyrste Křesomysls regjering. Horymírs siste ønske før døden var å kunne ri på sin trofaste hest, Šemík. De stengte portene var til ingen hinder, Šemík fikk det til og hoppet over festningsmuren med den tapre ridderen på ryggen og direkte inn i Vltava.