Kdy byl hrad postaven, nelze přesně určit,  místní historikové kladli jeho počátky do 12. století a spojovali jej s hradem Karpensteinem v Kladsku, který patříval rodu Glubošů a to na základě nálezu erbu na obytném paláci. Podle stavební struktury lze však říci, že hrad patří nejdříve do druhé poloviny 13. století.

 Dosti nepřesná zpráva uvádí, že olomoucký biskup Stanislav I. Thurzo vypravil na počátku 16. století proti hradu, silné vojsko, které jej dobylo a zbořilo. Jisté je, že někdy na přelomu 15. a 16. století, pravděpodobně v důsledku odlehlé polohy a jako nepohodlný, byl opuštěn a pomalu se změnil ve zříceniny.

Zříceninu hradu Rychleb opravili na počátku 20. století místní milovníci historie podle svých představ o vzhledu středověkých hradů. Zdi, patrné již jen v základech, podstatně zvýšili a místy do nich dosti libovolně zasadili okenní rámy, nalezené v sutinách. Ke zříceninám hlídkové věže přistavěli kamenné schody. Podobně upravili i zříceninu hlavní věže. Při této romantické úpravě zřícenin, kdy mohlo dojít i k částečnému porušení původního půdorysu, bylo nalezeno velké množství předmětů denní potřeby, z nichž větší část se však ztratila. Ke zvláštnostem patří tzv. destičková zbroj ze 14. století, dále zde byly objeveny zámky, dveřní kování, podkovy, hroty k šípům i groš z doby Jana Lucemburského. Zbytky keramiky svědčí o tom, že hrad byl obýván ještě v 15. století.

Podle pověsti tady řádil zlý duch v podobě rytíře,který lákal mladé dívky do hradu.Ty nechal,pak zahynout v hladomorně ,ale jedna dívka se mu zalíbila a tu si chtěl vzít za ženu.Ta odmítla a ani se nenechala vylekat pohledem na kosti svých předchůdkyň.Rytíř  sekerou zabil kněze,který je nechtěl oddat a vzbouření vesničané dorazili na hrad,Rytíř zaklel dívku v hada a sám uprchl