Původně označován německy "Haus", v roce 1335 je uváděn jako hrad (castum), podle Václava Hájka z Libočan je uváděn jako bájný hrad Sukoslav.

Nejstarší dochovaná zmínka je v kupní smlouvě z 19. prosince roku 1333, kdy Boreš z Riesenburku a jeho synové Boreš a Slávek prodali hrad Chotěborovi z Hirštejna. Za rok a půl tento šlechtic prodal tento majetek nástupci českého trůnu Karlovi, tehdy markraběti Moravskému. Ten však hrad udělil v léno věrnému svému Habartovi staršímu z Žerotína. Po něm zde vládli jeho příbuzní a potmci. V roce 1434 husitský válečník Jakoubek z Vřesovic tento hrad dobyl za pomoci svých spojenců a potom se domluvil s Albrechtem z Dubé o odkoupení hradu i s majetkem k němu přináležejícím, což potvrdil i císař Zikmund, na jehož stranu mezitím Jakoubek přestoupil. Pak zde působili jeho potomci, ale v roce 1562 byl hrad opuštěn. V té době potomci Krištofa z Vřesovic - Petr, Pavel a Oldřich - vystavěli dvě tvrze v Kostomlatech (tehdy byly Kostomlaty městečkem). Zde byli až do třicetileté války a pro účast na českém povstání přišli o svůj majetek. Tento zkonfiskovaný majetek byl v roce 1624 odprodán Humprechtu Černínovi z Chudenic. Černínové na místě dvou tvrzí vystavěli zámek.

V polovině 19 století byla v areálu dolního nádvoří zříceniny hradu zbudována restaurace a byla opravena a zpřístupněna turistům hlavní věž. Po roce 1948 byla hospůdka rozebrána.
V současné době je hrad přístupný na vlastní nebezpečí. Hlavní věž je nepřístupná. Areál hradu je udržován Občanským sdružením pro záchranu hradu Kostomlaty. Každý víkend zde sdružení drží službu a poskytuje turistům informace o hradě. Můžete zde i zakoupit drobné občerstvení a turistickou známku. Tu lze také zakoupit v Konzumu u Kasalů v obci.

Z věže hradu je překrásný výhled do údolí mezi Krušnými horami a Českým středohořím. Věž je bohužel nepřístupná, tak alespoň kviknutím myši na zmenšený panoramatický snímek si jej můžete vychutnat.

Ještě jeden pohled na hrad Kostomlaty z jeho dolního nádvoří, z míst, kde kdysi stála útulná turistická hospůdka.

Na hrad Kostomlaty vede od autobusového nádraží v Kostomlatech pod Milešovkou zelená turistická značená cesta (asi jeden km).

Více podrobností o tomto místě naleznete v Průvodci historií a památek z října 2002 z června 2003 a ze září 2005.