Velešínský hrad byl vybudován již na konci první třetiny 13. století jako královský hrad. Od Přemysla Otakara II. získal hrad Čéč z Budějovic, pak jej vlastnili páni z Michalovic a nakonec Rožmberkové. Třebaže na počátku 15. století prošel hrad stavebnímu úpravami, byl opuštěn již v roce 1487, za vlády Voka II. z Rožmberka. Příležitostně býval krátkodobě obýván zřejmě až do počátku 16. století, pak ale byl pobořen a nakonec se stal zdrojem stavebního kamene.3
Ani výzkumy archeologů nepřinesly odpověď na otázku, jak přesně hrad vypadal. Jisté je, že na skalnatém ostrohu obtékaném řekou Malší stál opevněný komplex protáhlého tvaru. Na západě se nacházelo širší volně svažité a na úpatí při řece rovinaté předpolí, na východní straně pak terén přechází do širšího (dnes zalesněného) svahu. Zatímco na severní i jižní straně proudila pod příkrými skalami Malše, na obou přístupnějších stranách chránily hrad dvojité hluboké příčné příkopy s náspy. Alespoň vnější příkop na východní straně, odkud v případě útoku hrozilo největší nebezpečí, zřejmě ještě bylo možno napustit vodou z rybníčků u Sedlce. Zbytky příkopů jsou v terénu dodnes zřetelné. Patrné jsou i pozůstatky dalších opevňovacích systémů – na výběžku ostrožny na západě se nachází vyvýšenina označovaná jako tvrz, která je považována za součást vnějšího opevnění hradu, na východní straně byl vlastní areál vnitřního hradu oddělen od předpolí hlubokým příkopem, na jehož vnější straně se dosud nacházejí zbytky objektů opevněného předhradí. Původní opevňovací soustava prošla podstatnými změnami počátkem 15. století, kdy byl například přemístěn padací most bránící vstup do hradu.3