Onegdaj mieszkał na zamku potomek fudatora warowni Spytko II Leliwita. Bardzo dzielny był to rycerz i dlatego też sprzyjała mu fortuna. W bardzo młodym wieku został wojewodą krakowskim, a za zasługi oddane krajowi otrzymał liczne włości. Poślubił też najpiękniejszą i najbogatszą dwórkę królowej Jadwigi. Aż nastał rok 1399. Spytko wyruszył na wyprawę na wschód i, jak doniesiono, zginął w bitwie z Tatarami. Żona Spytka nigdy nie uwierzyła w śmierć męża. Po prawdzie też nie odnaleziono ciała rycerza. Czekała na jego powrót 30 lat wypatrujac z murów melsztyńskiego zamku mężowskiej sylwetki, aż wreszcie postanowiła dokonać dni swoich w klasztorze. Niedługo potem, u bram zamkowych pojawił się jakiś ubogi starzec prosząc by go wpuszczono. Słudzy zamkowi jednak pozostali głusi na jego błagania. Podobno człowiek ów siedząc u podnórza murów powtarzał cicho imię pani zamku i jej dzieci, ale jego cichy głos nie docierał do zamkniętych wewnątrz sług. Powiadają, że mógł to być Spytek Leliwita, powracający po latach z tatarskiej niewoli, ale czy tak było w rzeczywistości? Któż teraz odgadnie?

         Zamek na wzgórzu nad Dunajcem zbudowany został przez kasztelana krakowskiego Spycymira w 1 połowie XIV wieku na planie nieregularnym. Według podań, murowana warownia wzniesiona została na miejscu wcześniejszego, drewnainego gródka, który istnieć tu miał już w XI wieku. Zamek posiadał wieżę mieszkalną, zabudowania dla służby oraz gospodarcze, otoczone murem. Nazwa zamku pochodzi podobno od położonych u jego stóp młynów (Mellstein - kamień młyński). Potomkowie Spycymira, od swej siedziby wzięli nazwisko Melsztyńskich. W XV wieku zamek stał się ośrodkiem husytyzmu w Polsce, a to za sprawą ówczesnego właściciela zamku, Spytka z Melsztyna, zwolennika husytyzmu. Potomkowie Spytka musieli długo zabiegać o zwrot skonfiskowanych po porażce husytów dóbr. W XVI wieku twierdzę przejęli Jordanowie, następnie Taszyccy, Tarłowie i Lackorońscy. W 2 połowie XVI wieku rozbudowano zamek w stylu renesansowym na rezydencję magnacką. Dobudowano kaplicę zamkową, nowe, wygodniejsze budynki mieszkalne, stajnie i spichlerz. Na dziedzińcu wykopano studnię. Warownia oparła się atakom Szwedów. Zniszczona została w czasie walk konfederatów barskich z wojskami carskimi około 1772 roku.
         Zachowały się fragmenty murów ścian i wieży oraz fosa.