Každého návštěvníka Žulové, jehož kroky zde míří poprvé, obvykle už z dálky zaujme bizarní kostel stojící na strmém ostrohu nad obcí.

K válcové věži z hrubého, neomítnutého zdiva - pozůstatku gotického hradu - se připíná světlá loď klasicistního kostela. Taková kombinace se opravdu jen tak nevidí. Kdy byl postaven hrad nad nevelkou slovanskou vesnicí Sestrechovice, přesně nevíme. S největší pravděpodobností to bylo krátce před rokem 1290. Tohoto data je totiž nejstarší zmínka, která se nachází ve fundační knize vratislavského biskupství. Z ní se také dovídáme o stavebníkovi, kterým byl Jan Wisthub pocházející odněkud z Franska. Spolu se svými bratry postavil i hrad Kolštejn v nedaleké Branné. Tato dvě místa se pak stala opěrnými body pro jeho pustošivé vpády do širokého okolí. Nebyl ušetřen ani Pačkov či vzdálené kladské pomezí.
Dalšími držiteli Frýdberka se od roku 1325 stali bratři Haugwitzové, kteří s veškerou vervou pokračovali v "díle" svého předchůdce: svou rodovou moc budovali loupeživými výpady. Během krátké vlády nad frýdberským panstvím (trvala do roku 1358) k němu připojili 11 vesnic a v blízkém okolí jich několik nově založených zpustlo. Konec jejich vlády učinil až biskup Přeclav z Pogarel, který od Haugwitzů hrad vykoupil za nemalý obnos 3100 kop pražských grošů. Hospodářský pokles po husitských válkách je donutil, aby Frýdberk přenechali jako léno či nájem jednotlivým feudálům.

V roce 1459 získal hrad jako zástavu Mikuláš Kotulínský, jehož potomci panství vlastnili až do roku 1537, kdy jej biskup s kapitulou vykoupili za 1100 uherských zlatých. Důvodem bylo hrozící turecké nebezpečí a hrad byl schopen ochránit čtyři míle okolní horské krajiny. Důležitou úlohu pro rozvoj frýdberského panství měl biskup Martin Gerstmann (1574 - 1585), jenž se rozhodl učinit hrad střediskem samostatného panství, které by bylo bezprostředně přičleněno k ostatním biskupským statkům. Proto jej dal v roce 1582 důkladně opravit, o čemž až do dnešních dnů svědčí pamětní deska zachovaná na zdi věže. Dalších oprav se hrad dočkal ještě v letech 1613 - 1620, kdy byly hradní věž i kaple, která vznikla již někdy na konci 14. století, zastřešeny a do věže byla zasazena skleněná okna.
Po třicetileté válce nastal naprostý úpadek panství. Hrad byl v roce 1640 obsazen švédskými vojáky, kteří na svém ústupu část hradu vyhodili do povětří a zbytek podlehl ničivému požáru. V obnovených obytných budovách byl o 50 let později, v roce 1703, zřízen pivovar. K jeho plánovanému rozšíření mělo dojít na konci 18. století. Žulovští měšťané však měli jiné plány.

Přestože byl roku 1793 Frýdberk povýšen na město, stále mu scházel vlastní svatostánek a Frýdberští občané museli na bohoslužby docházet až do sousedních Skorošic. Aby se plánovaná stavba kostela co nejméně prodražila, věnoval biskup Jan Kristián Hohenlohe pro kostel pozemek bývalého hradu. Dobře zachovaný hradní bergfrit měl sloužit jako zvonice. K němu se ještě před rokem 1810 přistavila jednoduchá kostelní loď a věž byla ukončena nástavbou s cibulovitou bání.

V 60. letech 18. století byl dosavadní dřevěný most nahrazen trvanlivějším kamenným a volně přístupné chodby hradu byly zasypány. O tom, jak vypadal celý objekt hradu, si v dnešní době můžeme udělat jen velmi mlhavou představu. Jan Wustehube, stavebník Frýdberka, využil přírodního terénu a dal jej postavit na ostrožně prudce spadající na severní straně a na jihu spojené úzkou šíjí s návrším. Šíje pak byla prokopána umělým hradním příkopem, přes nějž byl postaven most.

Celková dispozice hradu byla dvoudílná. Vlastní hrad byl vymezen prvním okruhem hradeb. Na přístupové straně byla postavena válcová věž o průměru více než 11 metrů, která se naštěstí dochovala v téměř původní podobě. Původní vstup ve výši prvního patra dnes ústí na kostelní kruchtu. Schodiště dále vede do dalšího podlaží. Přízemí věže je dnes upravené na vstup do kostela. Předhradí z velké části zmizelo v pozdější zástavbě. Zeď parkánu, který v jižní části - místě vstupu - tvořil předbraní, je ještě místy zachována.