Hrad Velešín je poprvé zmiňován v listině z roku 1266. V první třetině 13. století byl založen jako královský hrad – pravděpodobně Přemyslem Otakarem I. nebo Václavem I.
Výstavba hradu měla zřejmě pomoci posílit královskou moc v okrajových a málo obydlených částech říše, posádka se také patrně měla podílet na ochraně důležité obchodní stezky směřující do hornorakouského Freistadtu. V držení královské komory však hrad nezůstal dlouho. Roku 1265 vyměnil král Přemysl Otakar II. velešínské panství s Čéčem z Budějovic za Hlubokou a Budějovice. Čéč však Velešín zanedlouho prodal Benešovi Pyšnému. Jím zde začala vláda Michaloviců. Král Přemysl Otakar II. sice Benešovi Velešín odebral, ale Václav II. ho 28. srpna 1283 navrátil Benešovu synovi Janovi z Michalovic. Ve vlastnictví pánů z Michalovic pak Velešín setrval déle než jedno století.
V roce 1387 hrad, k němuž náležely Latrán a městečko na levém břehu Malše, vesnice Sedlce, Tolišovice, Chlum Polžov, Kladějov a další majetek, prodal Jan IV. Michalec z Michalovic Oldřichovi z Rožmberka. Ve vlastnictví Rožmberků se Velešín nacházel až do vymření rodu Petrem Vokem v roce 1611.
Do dnešní doby se dochovaly pouze zbytky opevnění a fragmenty půlválcové bašty a mohutné válcové věže, situované na úzkém skalnatém ostrohu nad řekou Malší. Zbytky velešínského hradu jsou volně přístupné.