Hrad vznikl zřejmě  před rokem 1293, byl stavěn způsobem, jaký byl v té době obvyklý.  Nechali jej vystavět Hückeswagenové, s jejichž hrady na Starém Jičíně či Hukvaldech má hodně podobností nebo olomoucký biskup Bruno ze Schauenburgu, čemuž by zase nasvědčovalo jeho stavění na naše končiny v jiném stylu? Podoba s Jičínem a Hukvaldama je shodná převážně v použití strážní věže (bergfritu). I na Šostýně stála výstražně namířena proti příchozímu v čele nad cestou přes dřevěný most, jistěže v poslední části zvedací.Spolu s docela malým dvorkem a strážnicí pro posádku byla vysloveně obrannou částí – jakýmsi "hrádkem". Teprve za ní se vcházelo po druhém mostě nad příkopem do zřejmě věžovité brány s propadlištěm, zčásti vytesaným do skály, jež se z ní jediné zachovalo. Hned za branou bylo obytné stavení a nevelký dvůr. V jižní části nádvoří stál palác, jehož suterén se dodnes zázračně zachoval a tvoří tak nejlépe zachovalou část hradu.

Zatímco Starý Jičín a Hukvaldy byly hrady výšinnými, stojícími na osamělých kopcích, Šostýn vyrost ve stínu Pískovny a byl vůči ní v ne právě výhodné poloze. To snad zavinilo v dobách vyspělejší dobývací techniky jeho ztečení a rozboření. Výše popsanému jádru, rozprostírajícímu se na dvou vrcholech – jižním s palácem a dvorem a severním s útočištnou věží – předcházelo předbraní a rozsáhlé předhradí. Hrad měl tak délku ve směru severojižním více jak 100 metrů a mohl se srovnávat rozlohou i s královským Lukovem nebo Cvilínem. Vnitřní hrad obepínal příkop a mohutný val – na jihu, západě a východě zdvojený – s nezbytnou palisádou. Než se příchozí dostal až sem, musel zdolat nejspíš ještě dva opevněné pahorky spojené mosty.
Palác měl nejméně jednu kamny vytápěnou místnost – rytířský sál – s dlažbou s motivem dubového listu a snad v prvním patře i okno na jih či západ. Jinak bývaly místnosti na hradech osvětlovány zásadně jen ze strany nejbezpečnější, nádvořní. Jižně od paláce je výrazná plošina na níž byla posledním výzkumem doložena kamenná parkánová zeď. Za palácem, ve svahu mimo samotný val, stávala ještě jedna plošina nesoucí kdysi dávno nějakou, zřejmě strážní dřevěnou budovu.

Studna na hradě asi nikdy nebyla a vodu brali z cisterny. Podle zvyku se do této sváděla soustavou dřevěných okapů ze střech, protože jí bývalo na hradech vždycky spíše méně než dost.
Přesný rok zániku Šostýna nelze určit a zřejmě se též nestalo najednou. Válčilo se před ním a o něj až do roku 1422, kdy jej na Mikuláši z Lamberka snad musel vojensky vymoci biskup olomoucký. Protože první zmínka o zřícenině je z roku 1437, je zřejmé, že hrad zanikl v rozmezí těchto patnácti let. Není vyloučeno, že byl hrad dobyt husitským vojskem Jana Tovačovského z Cimburka v roce 1427. Hrad Šostýn se rozpadal, pustnul rok od roku a co bylo na kopci, kde stával, ještě k upotřebení a neshořelo při požáru, jenž vždy dobývání provázel, pilně snášeli obyvatelé Kopřivnice i vzdálenějších vsí, aby dosloužilo jinde.
Od 30. let 20. století započal na Šostýně intenzivní archeologický a záchranný průzkum, jež odkryl hlavní část hradu, suterén velkého paláce, a po menších přestávkách opět naplno začal v 90. letech 20. století. Město Kopřivnice zaštítilo archeologický výzkum na hradě, stejně jako konzervátorské práce, jež na hradě probíhají dodnes. Velkým počinem bylo obnovení středověkého rybníka, který byl objeven v roce 1999.