Pierwsza wzmianka o „zamku Przymiłowice” (późniejszym Olsztynie) pochodzi z 1306 roku. Wzniesiony został na miejscu wczesnośredniowiecznego grodu, rozbudowany w latach 1349-59 z inicjatywy Kazimierza Wielkiego, dla obrony pogranicza śląsko-małopolskiego. Od 1370 r zamek przeszedł w ręce Władysława Jagiełły.
Od 1406 roku warownia stanowiła siedzibę starostwa niegrodowego i posiadała stałą załogę wojskową. Pierwszym starostą był Paweł Odrowąż. W połowie wieku XVI, za czasów starosty Mikołaja Szydłowieckiego twierdza nabrała cech renesansowych.
W 1587 r zamek zniszczyły wojska Maksymiliana Habsburga – pretendenta do polskiej korony, choć nie zdobyły warowni. Kolejne zniszczenia nastąpiły podczas ataku szwedzkiego w roku 1656. Od tego czasu zamek ulegał ruinie, skały wapienne kruszyły się naruszając mury, a ponadto dolne partie zamku w latach 1722-29 rozebrano, by uzyskać materiał na budowę kościoła w Olsztynie.
W 1818 roku z tutejszych dóbr utworzono olsztyńską ekonomię dóbr rządowych. Do dziś zachowały się riuny w postaci wieży i fragmentów murów.
W czasie swej świetności (XVI w) zamek składał się z 5 zasadniczych części: dwu przedzamczy oraz zamku dolnego, środkowego i górnego. Po pd-wsch stronie wzgórza znajdował się wjazd, który prowadził przez most zwodzony oraz bramę, umieszczoną w wieży, połączoną z murami obronnymi. Dalej znajdowało się pierwsze, wydłużone podzamcze z zabudowaniami gospodarczymi. Od zamku dolnego oddzielone ono było murem z bramą. W zamku dolnym stały budynki gospodarcze oraz dom mieszkalny zwany Kamieńcem. Kolejna brama prowadziła do zamku średniego, usytuowanego u podnóża okrągłej wieży. Ta część z zamkiem górnym połączona była mostem zwodzonym nad sofą i bramą w murze przy wieży. Umieszczono tutaj kuchnie i trzy tzw. pokoje królewskie (sypialnia, jadalnia i sala sądowa).
Charakterystycznym elementem ruin jest gotycka baszta (donżon) z II połowy XIII wieku o wysokości 35 m, w dolnej części okrągła, w górnej ośmiokątna, z kamienia, a w XV w nadbudowana z cegły. Służyła jako więzienie, zmarł w niej śmiercią głodową Maćko Borkowic – wojewoda poznański z rozkazu Kazimierza Wielkiego. Drugie podzamcze znajdowało się w części pd-zach, z kwadratową basztą obserwacyjną zw. Sołtysią. Cały zamek otoczony był murem obronnym.
Warownia olsztyńska jest przykładem gotyckiej budowli zamkowej (typu wyżynnego), w jej konstrukcję włączono wapienne ostańce oraz krasowe groty, co pozwala ją zaliczyć do grupy zamków jaskiniowych.
W ciągu ostatnich lat ruiny zamku w Olsztynie były miejscem niespotykanego spektaklu przyciągającego tłumy ludzi spragnionych wrażeń. Raz do roku, jesienią odbywał się tutaj festiwal sztucznych ogni i laserów rozjaśniających czarną noc…