Nejstarší písemná zmínka o hradě Kolštejn, postaveném v blízskosti obchodní stezsky ze Slezska do Olomouce, pochází z roku 1325. Touto listinou daroval majitel hradu Jan Wustenhube rozsáhlé pozemky, obec a hrad Kolštejn ve slezském Kamenci. hrad byl zřejmě postaven v letech 1308-1310 v období bezvládí po vymření Přemyslovců za účelem loupežení a kořistění, po té vzniklo patrně i městečko Kolštejn. Právě z té doby se za hradbou nacházela stojící okrouhlá věž, tzv. bergfrit, jejíž fragmenty jsou patrné dodnes.

Ve 30. letech 14. století patřil hrad českému králi Janu Lucemburskému, který jej roku 1339 daroval Pertoldu z Lipé. Koncem 14. století získali panství a hrad páni z Valdštejna, z nichž v předhusitském a husitském období proslul Hynek zvaný také Kolštejnský. Hrad Kolštejn se stal jeho hlavním sídlem a hrál významnou úlohu za husitských válek. Ve službách císaře Zikmunda byl však Hynek v září 1427 zabit a poté získal Kolštejn Markvart ze Zvole.

Právě za pánůze Zvole dostal hradní areál svou konečnou podobu. Ve východní části hradu byl postaven nový palác a bylo vybudováno rozsáhlé opevněné předhradí severně od hradního jádra. Patrně tehdy byla také postavena gotická vstupní věže, která byla renesančně přestavěna v 16. století.

Po smrti Václava ze Zvole přešlo panství na jeho setsru Barboru, která přenechala část panství svému choti Janu Černickému z Kácova. Ten ho v roce 1575 prodal Karlu staršímu ze Žerotína. Roku 1578 musel Karel, patrně pro velké dluhy, přenechat kolštejnské panství svému bratrovi Janu ml. ze Žerotína. Ten zemřel bezdětný a jeho sestra Bohunka panství v roce 1581 prodala spřízněnému rodu Bruntálských z Vrbna. Za obou Žerotínů byl areál středního hradu postupně přebudován na zámek.

Následně panství zakoupil Hynek starší Bruntálský v Vrbna. Ten v roce 1584 vydal pro poddané kostelní, školský a sňatkový řád, kterým na kolštejnské panství zavedl luteránskou víru. Po jeho smrti převzal roku 1596 panství jeho syn Jan starší, který studoval na švýcarských kalvinistických univerzitách. Po návratu a převzetí panství byl činný i politicky, v letech 1601 – 1603 byl správcem nejvyššího hejtmanství markrabství moravského. Jeho dva synové, Hynek ml. a Bernart, společně drželi Kolštejn v letech 1608 – 1614. Nedaleko zámku vystavěli nový kostel, nynejší farní kostel Archanděla Michaela, původně však zasvěcený Zmrtvých vstání Krista.

Hynek ml. Bruntálský z Vrbna byl aktivní v politice, v letech 1608 – 1614 zastával úřad zemského hejtmana. V únoru 1610 navrhoval přemístění Zemských desek na zámek v Bruntále a v případě vyhrocené situace na Kolštejn, což svědčí o významu a pevnosti hradu a zámku Kolštejn ve své dobe. Nedostatek času, politická funkce a vysoké náklady při stavebních úpravách, kdy byla dobudována vstupní „Černá věž”, tzv. Horní zámek s unikátní sgrafitovou výzdobou a upraveny interiéry zámku, způsobily, že panství bylo silně zadluženo. Po Hynkove smrti prodali poručníci jeho nezletilých synu kolštejnské panství Hanuši Petřvaldskému z Petrvaldu za 130 000 zlatých.

Luterán Hanuš Petřvaldský z Petřvaldu se aktivne podílel na stavovském povstání, byl členem zemského direktoria, zemským soudcem a komisarem pro prodej církevních statků. Za jeho držby byl dostavěn tzv. Dolní zámek, celá budova byla sjednocena slohove jednotným arkádovým nádvořím s fontánou se symbolikou apokalypsy na patkách arkád a s maskarony ďáblů a čarodějnic. Nechal také vybudovat manýristický portál
do dvora vstupní věze se znaky manželů a hlavou Turka nabodnutou na kůlu.

Po bitvě na Bílé hoře došlo ke konfiskaci kolštejnského panství. To získal jako léno Koruny České Karel z Lichtenštejna. Tím Kolštejn ztratil svou obytnou a reprezentační funkci a už se pak nikdy sídlem šlechty nestal, protože Lichtenštejnové meli spoustu jiných sídel.

Za třicetileté války se Kolštejn stal významným opěrným bodem císařských vojsk a sídlem početné posádky. Bylo rychle dobudováno opevnené předhradí smerem k městecku, kde byly za branou chráněnou válcovou věží po stranách nádvoří soustředěny stavby panských úřadů. Po třicetileté válce se však Kolštejn stal pouze hospodářským sídlem správy panství a s postupující centralizací lichtenštenských velkostatků v 18. a 19. století klesal i význam zdejšího vrchnostenského úřadu.

Obec Goldenstein (Kolštejn) získala zámek po roce 1918. Za druhé svetové války bylo toto území součástí severovýchodních Sudet. Na zámku byla vojenská posádka, škola, další prostory byly nevyužívané. Po roce 1945 došlo ke změně názvu obce na Branná. Prostory zámku sloužily jako sklady léčiv, škola a tělocvična.
S pokusy o rekonstrukci zámku bylo započato v první dekádě nového milénia, protože však chyběly potřebné finanční prostředky, zámek zůstal prázdný. Nově zrekonstruován a přestaven byl až v současné době.