Jihovýchodně od vsi Kostomlaty p. Milešovkou stával na kopci hrad, jehož zbytky se dochovaly dodnes. Ves se připomíná poprvé v r. 1333 jako příslušenství oseckého panství. Také hrad stál snad již v roce 1933 a je označován německy Haus, avšak už v roce 1335 je uváděn jako hrad (castrum). Dřívější vlastivědní autoři ho ztotožňovali s vybájeným hradem Sukoslavem kronikáře Václava Hájka z Libočan.

Hrad postavili páni z Oseka,. Přístupová cesta k němu vedla od severovýchodu přes předhradí k bráně vnějšího dolního hradu, která je chráněna vlevo stojící okrouhlou věži, přístupnou v prvním patře z ochozu hrady a ve čtvrtém patře opatřenou hrázděným podsebitím. Dolní hrad uzavíraly zdi na severní, západní a jižní straně, na východě se vstupovalo přes příkop do vnitřního dolního hradu. Horní hrad, který stál na vyvýšeným místě hradního areálu, chránil z jižní a východní strany kromě hradeb i parkán. V jihozápadním rohu stála okrouhlá věž, nejvyšší část hradu, tvořící po dnes jeho typickou siluetu.

Věž byla původně přístupná také z vyššího patra. V jejím severním sousedství stál obytný palác, ve východní části hradu byla další budova,

Během vývoje došlo k zvětšení paláce a k přístavbě dvou bašt při jižním okraji parkánu. V roce 1333 dali páni z Oseka hrad Kostomlaty v lénu Chotěborovi z Herštejna. Příslušenství hradu nebylo veliké, náležely k němu vesnice Kostomlaty pod Milešovkou, Rtyně nad Bílinou, Mrzlice, Hlince a Velvěty. Roku 1335 koupil hrad s panstvím markrabě Karel, později císař Karel IV. To je také první hodnověrná zpráva o hradu.

Roku 1370 byl pánem na Kostomlatech Habart starší ze Žerotína, jehož nástupco prodali panství roku 1388 Jindřichu Škopovi z Dubé. Na počátku husitských válek držel Kostomlaty Albrecht Škopek z Dubé, velký kontur řádu německých rytířů v české provincii. Páni z Dubé se již v prvních letech 15. století dohodli s míšenským markrabětem, že kostomlatský hrad mu bude ve všech válkách otevřen. V letech husitských válek Albrecht Škopek hrad proti husitům udržel. Byl však silně poškozen roku 1434 v době bitvy u Lipan. Panské vojsko, které se vítězně vracelo z lipanské bitvy, pobídnuto Zikmundem z Wartemberka na Děčíně utkalo s Jakoubkem ve snaze vymanit Kostomlaty z obléhání. Jakoubek nebyl v boji příliš úspěšný, jelikož na bojiště vpadla neočekávaně ze zálohy panská pěchota. Roku 1435 se však uvádí jako držitel hradu.Své další sporty, které měl o hrad s pány z Dubé, vyhrál a celá jedna linie jeho potomstva se pak nazývala Kostomlatští z Vřesovic.

Zahájil ji Jakoubkův syn Jakub, který se ujal dědictví roku 1468, Po roce 1562 patřilo ke hradu již jen městečko Kostomlaty. Počátkem 17. století se dělili o kostomlatské panství bratři Petr a Oldřich Kostomlatští z Vřesovic a každý měl ve své polovině městečka tvrz. Hrad mezitím zpustl, roku 1606 byl neobydlený a Oldřich z Kostomlad byl postižen konfiskací jedné třetiny majetku pro účast na stavovském povstávní z let 1618-1620. Podle tehdejší praxe bylo však prodáno celé panství, které koupil v roce 1624 Humprecht starší z Černína z Chudenic. Černín přikoupil ještě konfiskované Černčice a později Lhenice a Bukovice. Kostomlatský hrad byl podle svědectví Bohuslava Balbína koncem 17. století opět obýván. Roku 1841 byl dolní část nádvoří částečně zrestaurován

Podle pověsti husitský vůdce po bitvě u Lipan přešel na stranu Zikmunda. taková zrada mu ovšem projít nemohla a tak prý o půlnoci bloudívá duch proradného Jakoubka s černou skvrnou na čele v podobě kalicha ve zříceninách hradu a marně hledá věčný klid.