První hodnověrná zmínka o Kaltenštejně pochází z roku 1295. Toho roku jej vykoupil Bolek I. Svídnický od odpůrců vratislavského biskupa, kteří jej nejspíše krátce před tím vystavěli. Vzápětí byl hrad navrácen do biskupských rukou. V té představoval jednoduchou bergfritovou dispozici, za okrouhlým bergfritem na nejvyšším místě kopce stál dvoudílný palác a celek byl obklopen obvodovou hradbou se vstupní bránou. Snad již v této fázi měl hrad na severozápadě dvoudílné odstupňované předhradí.
V následujících letech byl hrad často zastavován, aby se vždy po určíté době vrátil do biskupských rukou.
Z období husitských válek nemáme o hradě zprávy, zdá se však, že na rozdíl od jiných míst nepadl husitům do rukou. Zato v roce 1441 se jej zmocnil dobrodruh Zikmund Rachna, který dokonce unesl dceru královského hejtmana Půty z Častolovic. Biskupské oddíly hrad oblehly a dobyly. Zikmund byl zajat a přímo na hradě umučen. Poškozený hrad byl sice opraven, ale v dalších letech ztrácel na významu, až byl někdy po roce 1505 pobořen, snad v souvislosti s přestavbou nedalekého Jánskéhu vrchu. Při demolici byl intenzivně použit střelný prach, který má na svědomí roztržení bergfritu a následné rozmetání velkých kusů zdiva po celém areálu hradu. V době svého zániku se Kaltenštejn příliš nelišil od již popsaného stavu, změny se týkaly především předhradí, které bylo obklopeno novým pásem hradeb s branskou budovou a nevelkou čtverhrannou baštou v její blízkosti.
V nepravidelném jádru volně stojí polovina okrouhlého bergfritu o průměru 10,8 m, roztrženého výbuchem. Přízemí téměř čtvercového dvoutraktového paláce bylo zaklenuto valenými klenbami. Kolem jádra jsou zbytky zdiva parkánu, jímž na severu procházela přístupová cesta. Na severozápadě bývalo předhradí, rozvalené zdivo potvrzuje záměrnou demolici. Viditelný je průběh vnější ohrady s malou hranatou baštou na jihozápadě.
Kaltenštejn se vypíná nad nedalekou obcí Černá Voda na Jesenicku, jejíž český i německý název (Schwarzwasser) je odvozen od barvy písku na dně místního toku. Mají tu i malý pozdně renesanční zámeček vybudovaný po roce 1618.
Jak se zde dostanete?
Můžete přijet autobusem z Jeseníku, nebo i vlakem. Pokud pojedete vlakem z Jeseníku, musíte v Lipové lázni přestoupit. Vlakem směrem do Javorníku se vydáte do Žulové. Dále do Černé Vody autobusem.