Hrad Frýdberk stával na kopci nad městečkem Žulovou (do r. 1948 Frýdberk) v místech dnešního kostela sv. Josefa. Válcová kostelní věž, postavená z hrubého neomítnutého zdiva, budí na první pohled představu středověkého hradu, zatímco jednoduchá bílá loď připomíná střízlivost kostelních staveb z období josefinismu. Jde vskutku o původní hrad, vzniklý krátce před r. 1290.

Hrad Frýdberk stál na vysokém ostrohu, který prudce spadá na severní stranu, kdežto na jihu je spojen s návrším, na němž se rozkládá městečko. Vzhledem k pozdější úpravě terénu kolem židovského kostela nelze již podobu hradního areálu přesně určit, možno jen soudit podle konfigurace terénu, že přístup k němu vedl po šíji spojující návrší, na kterém je městečko, s hradním areálem. Šíje byla prokopána umělým hradním příkopem, přes nějž dnes vede do areálu někdejšího hradu kamenný most. Z hradu se zachovala pouze neomítnutá kamenná válcová hradní věž.


Stavebník hradu Jan Wüstehube se stal spolu se svými bratry postrachem pro široké okolí, protože nelítostně plenil oblast od moravského Kolštejna, který mu rovněž náležel, až po Otmuchov. V r. 1318 vnikl se svými společníky v městě Páčkově do kostela a při bohoslužbách ubil několik lidí. Nebylo divu, že Wisthubova družina žila s biskupy v otevřeném nepřátelství.

Rovněž další držitelé hradu – od r. 1325 bratři Rüdiger, Václav a Jindřich Haugwitzové, jimž patřil do r. 1358 – budovali svou rodovou moc loupežemi a násilím. Proto se biskup Přeclav z Pogarel rozhodl zbavit kraj této zhouby a raději se vzdal starobylého biskupského kastelánství Milice, aby za získané peníze koupil v r. 1358 od bratrů Václava a Jindřicha Haugwitzů Frýdberk za značnou sumu 3100 kop pražských grošů.  

Nově zakoupené panství svěřovali biskupové purkrabím. Patrně teprve po převzetí hradu biskupy byla zde přistavěna kaple. Nájemci hradu se pak skoro pravidelně po třech letech střídali.Biskup Martin Gerstmann (1574–1585), věnující velkou péči hospodářské obnově biskupských statků, se nakonec rozhodl trvale k nim přivtělit hrad a učinit jej střediskem frýdberského panství. Proto jej dal v r. 1582 důkladně opravit a do zdi válcové věže zasadit pamětní desku. Podle jejího textu lze soudit, že hrad byl poškozen válkami i ohněm (zprávy o něm však mlčí). Brzy se ale ukázalo, že samostatná správa nevelkého frýdberského panství je příliš nákladná, a proto byl hrad s příslušenstvím připojen k Jánskému Vrchu pod společnou hejtmanskou správu.


V letech 1613–1620 byly hradní věž a kaple nově zastřešeny a do věže zasazena skleněná okna. Za třicetileté války zůstal hrad zprvu ušetřen bojů. V r. 1639 však vpadla do nisko-otmuchovského knížectví švédská vojska s Poláky a Němci, dobyla Otmuchov a Jánský Vrch a počátkem července se obrátila i proti Frýdberku. K jeho dobytí stačil malý oddíl rejtarů. Když se o tom dověděl bojovný Jindřich Obergk, hejtman ve Frývaldově (nyní Jeseník), vyzbrojil 60 měšťanů a náhlým přepadem švédskou posádku překvapil. Jejího velitele sice zabil, ale zbytek se stáhl do věže a vyčkal v ní až do příchodu posil z Jánského Vrchu. Když hlavní část Švédů opustila Otmuchov, ustoupila i jejich posádka z Frýdberku, napřed však vyhodila část hradu do povětří a zbytek zničil vzniklý požár.

V r. 1650 už hrozilo hradu úplné rozpadnutí. Ze zřícenin byly obnoveny obytné budovy, v nichž byl od r. 1703 umístěn pivovar, a hradní kaple. Z hradeb vyrůstaly stromy; tento pohled na hrad byl pojat i do obrazu městské pečetě, když byl Frýdberk v r. 1793 povýšen na město (zřícenina hradu s malou jedlí na vrcholu válcové věže). Majetkem vratislavského arcibiskupství zůstal frýdberský velkostatek až do r. 1948.

Hrad Kaltenštejn byl svědkem smutného konce rytíře Zikmunda Rachny

Biskup Jan Kristián Hohenlohe (1789–1817) daroval pro kostel pozemek bývalého hradu s dobře zachovalou věží. K té byla přistavěna jednoduchá kostelní loď a věž byla ukončena kratší nadstavbou s cibulovitou bání. Stavba kostela byla dokončena r. 1810. V 60. letech 19. století byly volně přístupné podzemní chodby hradu zasypány, dřevěný most nahrazen kamenným a zbytky hradní zdi byly zpevněny opěrnými pilíři.