A Füzéri vár 1389. február 2-án, Zsigmond király adományaként került a Perényiek birtokába. A mohácsi csatából szerencsésen megmenekülő Perényi Péter, mint koronaőr, Szapolyai János koronázása után a koronát nem a szokott őrzési helyére (Visegrádra) vitte, hanem Füzéren helyezte el, ahol csaknem egy esztendeig őrizték azt. Szapolyai bosszúja 1527 őszén már Perényi terbesi, pataki és füzéri birtokainak fenyegetéseként jelentkezett. 1529-ben-ben, Szapolyai elől Siklósról menekültében Perényit, annak Ferenc nevű fiával együtt Szapolyai elfogta, majd átadta őket Szulejmán szultánnak. Perényi nagy nehezen kiszabadult a rabságból, de Ferenc fia túszként Szulejmánnál maradt, ahonnan később Isztambulba került. (Perényi Ferenc további sorsa tisztázatlan, de ezen a történeten alapul egy füzéri, vagy még inkább pusztafalui legenda.)

1547-ben felbukkant egy személy, aki saját maga állítása szerint azonos volt az 1529-ben a töröknek túszul hagyott Perényi Ferenccel. Kezdetben hitelt adtak neki, (maga Perényiné is elismerte a fiának), utóbb azonban kétségbe vonták állítását. Perényi Péter halála után az egyetlen vitathatatlan örökösöknek, másik fiának, Perényi Gábornak első dolga volt tisztázni a problémát. 1548 májusában az esztergomi káptalan emberei Füzéren kihallgatták az állítólagos Ferencet, aki ekkor Poór Mihálynak, esztergomi polgárszülők gyermekének vallotta magát. így tehát az „elveszett” Ferenc további sorsa legendaként maradt fenn: a nép „megírta” a Perényi-fiú történetét, s ezen keresztül Pusztafalu, mint település magalapításának históriáját is.

A szájhagyomány szerint a 16. század végén két, egymástól gyermekkorban elválasztott Perényi-fiú, külön-külön török fogságba esvén Isztambulban találtak egymásra. A szultán elálmélkodva a csodálatos találkozáson, mindkettőjüket hazabocsátotta ősi birtokukba, a füzéri várba, sőt tatár segédcsapatokat is adott melléjük kísérőül.

A monda szerint a Perényi-fivérek a tatárokat letelepítették a Füzérrel szomszédos Pusztafaluban, s leszármazottaik ma is ott élnek. Ezek a tatárok a Füzér és Pusztafalu között magasodó őrhegyen egy őrhelyet emeltek, melynek sáncai a mai napig láthatóak.