Pierwsza wzmianka o zamku olsztyńskim (wtedy identyfikowanym jako zamek w Przemiłowicach) pochodzi z roku 1306 a zawarta została w aktach drugiego procesu biskupa krakowskiego Jana Muskaty, wytoczonego mu w roku 1306 przez arcybiskupa gnieźnieńskiego, Jakuba Świnkę. Z tego też powodu w 2006 roku obchodzono Jubileusz 700 lecia Zamku Olsztyńskiego. Pierwsza wzmianka o Zbyszku, burgrabim olsztyńskim pochodzi z 1349 r. Istniejącą od drugiej połowy XIII wieku strażnicę rozbudował w XIV wieku Kazimierz Wielki jako jeden z najbardziej warownych zamków na pograniczu śląsko-małopolskim. Według tradycji za jego panowania więziony był w zamku wojewoda poznański Maćko Borkowic, który zmarł w niej skazany na śmierć głodową za zorganizowanie spisku przeciw królowi. Według podań duch wojewody, jęki, brzęk kajdan i zawodzenia do dziś mają straszyć w okolicy zamku.

W 1370 r. król Ludwik Węgierski przekazał Olsztyn z ziemią wieluńską w lenno swemu siostrzeńcowi, księciu opolskiemu Władysławowi Opolczykowi za popieranie swych planów dynastycznych. W 1391 r. Władysław Jagiełło po tygodniowym oblężeniu zdobył zamek i przywrócił go Koronie. W 1406 r. podgrodowa osada nazywana wówczas Olsztynkiem została siedzibą starostwa. W 1488 r. Kazimierz IV Jagiellończyk nadał jej prawa miejskie. W XV wieku zamek odegrał znaczącą rolę przy odpieraniu napadów ze strony książąt śląskich. W tym czasie został rozbudowany, potem był kilkakrotnie przebudowywany z powodu kruszenia się murów wskutek osuwania się skał. W 1552 Olsztyn uzyskał przywilej na targi i jarmarki. Miasto nigdy nie rozwinęło się ze względu na nieurodzajną, piaszczystą glebę oraz położenie z dala od szlaków handlowych.

W 1587 r. atakowany był przez wojska austriackie arcyksięcia Maksymiliana, pretendenta do tronu polskiego. Dowódcą załogi był wówczas starosta Kacper Karliński. Jego porwany kilkumiesięczny syn wraz z piastunką wystawiony został pod zamek na pierwszą linię ognia. Obrona się powiodła, z poświęceniem jednak życia syna dowódcy. Doszło też do zniszczeń zamku. Wydarzenie to znalazło swój wyraz w twórczości Władysława Syrokomli i Aleksandra Fredry.

W 1656 r., w czasie potopu, Szwedzi zrujnowali zamek i spalili miasto. Był to początek jego upadku. W latach 20. XVIII wieku rozebrano duże fragmenty dolnych partii zamku. Do końca tego stulecia przetrwało starostwo olsztyńskie. Wkrótce także odebrano Olsztynowi prawa miejskie.

Do dziś z zamku zachowały się mury części mieszkalnej, wieże: cylindryczna (stołp) i kwadratowa (Starościańska), fragmenty murów budynków gospodarczych, częściowo także piwnice oraz odkryte w czasie badań archeologicznych fundamenty kuźnicy i ślady dymarek. W latach 1992–1993 oraz 1995–1998 odbywał się tu międzynarodowy pokaz pirotechniki i laserów. Po zawaleniu się fragmentu muru zamkowego konserwator zabytków zakazał tego typu imprez. Ruiny zamku udostępnione są do zwiedzania.