První zmínka pochází z roku 1316. Sídlil zde rod, který se nazýval z Gutštejna.
V roce 1422 čelil hrad husitskému vojsku, ti se jej marně pokoušeli dobýt. Počátkem 15. století začal být hrad pro mocný rod příliš těsný. Funkce hradu a vliv nad panstvím byla přenesena na pohodlnější Bezdružice.
Roku 1566 se Gutštejn uvádí jako pustý. Z nejstaršího období hradu se dochovala 25 metrů vysoká věž. Výrazné jsou zbytky jižního a severního paláce. Jako každý hrad má vlastní pověst i u Gutštejna tomu není jinak. Říká se, že zde bloudí přízrak Bílé paní a mnicha. Pán hradu prý po pitce mnicha zabil, ten tu čeká na vysvoboditele dobrého srdce.
