Krásna Hôrka vznikla na ochranu cesty do baníckej oblasti Slovenského rudohoria. Vzhľadom na jej strategickú polohu sa predpokladá, že bola postavená na mieste hradiska, o ktorom sa však nezachovali nálezy ani historická zmienka. Podobne staré slovanské hradisko potvrdzujú nálezy na neďalekom vrchu Drieňovec (nad obcou Drnava), ktoré pravdepodobne plnilo strážnu funkciu pred postavením Krásnej Hôrky. Toto hradisko poskytlo útočište kráľovi Belovi IV., keď utekal pred Tatármi po osudnej bitke pri rieke Slanej roku 1241.
Kamenný gotický hrad postavil okolo roku 1320 rod Mariássyovcov, ktorý kúpil územie Krásnej Hôrky od Bebekovcov. Ako vlastníci baní na Spiši chceli jeho vybudovaním zabezpečiť ochranu spišsko - gemerskej obchodnej cesty. Po postavení hradu však Bebekovci napadli zmluvu o predaji a nastali ťahanice o vlastníctvo hradu. Roku 1352 Bebekovci spor vyhrali a Krásna Hôrka sa stala ich majetkom až do roku 1566, keď posledný člen rodu odišiel do Sedmohradska.
Pôvodný hrad tvorila veľká obytná veža a gotický palác postavené na najvyššom mieste kopca a obohnané opevnením. Na sever od paláca ležalo hradné nádvorie s cisternou (dnešný horný hrad).
Na dvadsať rokov sa stala Krásna Hôrka vlastníctvom Jána Jiskru z Brandýsa. V tomto čase prebehli na hrade mnohé opevňovacie práce. Potom bola Krásna Hôrka opäť majetkom Bebekovcov.
V období od 1544 vzhľadom na turecké nebezpečenstvo dal Štefan Bebek vybudovať nové renesančné opevnenie, ktoré malo tri kruhové bašty. Najvačšia z nich, tzv. Dobogó bašta, chránila vstup do hradu. Medzi baštami na východnej strane bola vybudovaná široká delová terasa, na ktorej dodnes stoja ťažké delá odliate v rokoch 1545 a 1547. Súčasne s novým opevnením upravili interiéry starého hradu, ktorý dostal goticko-renesančný charakter. Prestavba bola okolo roku 1546 dokončená.
František Bebek začal zbíjať po okolí, raziť si vlastné peniaze a napokon odoprel poslušnosť panovníkovi Ferdinandovi. Ferdinand vyslal proti Bebekovi vojsko, ale Bebek sa spojil s Turkami a v roku 1556 cisárske vojsko zahnal k Rožňave. Pozícia Bebekovcov však bola neistá a tak František Bebek odišiel do Sedmohradska, aby sa tu s tureckou pomocou stal ríšskym správcom na dvore maloletého kráľa Jána Žigmunda. Bol tu však zavraždený. Jeho syn Juraj Bebek chcel opäť nadobudnúť priazeň Ferdinanda a tak sa postavil do otvoreného boja proti Turkom. Nevedel si však získať jeho dôveru a tak sa v roku 1566 utiahol do Sedmohradska, kde umrel bez potomkov a tak vymrel mocný rod Bebekovcov.
Krásna Hôrka po odchode Juraja Bebeka prepadla štátu a dostala sa do správy hradných kapitánov. V roku 1578 sa hradným kapitánom stal Peter Andrássy, ktorý investoval veľa peňazí na prebudovanie hradu na pevnosť. Andrássyovci sa ho usilovali získať do svojho vlastníctva, čo sa im v roku 1642 podarilo. Od roku 1676 sa Krásna Hôrka stala sídlom župy a bola prebudovaná na renesančné sídlo.
V období protihabsburských povstaní začiatkom 17. storočia bol majiteľ Krásnej Hôrky Andrássy jediným zemepánom v Gemeri, ktorý sa v roku 1666 nezúčastnil Vesselényho sprisahania. Keď sa však v roku 1678 zmocnil hradu Thököly, prinútil Andrássyho pridať sa k povstalcom. Preto roku 1685 obliehalo Krásnu Hôrku cisárske vojsko, ale neúspešne.
V 18. storočí stratila Krásna Hôrka svoj strategický i vojenský význam a stala sa súkromným sídlom rodiny Andrássyovcov. V rokoch 1731 - 1770 bola prebudovaná, aby lepšie vyhovovala vtedajším podmienkam na bývanie. Významnou bola prestavba Dobogó bašty na barokovo - klasicistickú kaplnku v roku 1770. Išlo o poslednú úpravu pred vyhorením hradu, ktorý v roku 1817 podpálil blesk. Mária Andrássyova - Festetičová ho dala núdzovo opraviť, avšak hrad ostal v takomto stave takmer sto rokov neobývaný. Až začiatkom 20. storočia dal Dionýz Andrássy po smrti svojej manželky hrad zrekonštruovať (1903 - 1905) a umiestnil do neho rodové múzeum. V roku 1910 bolo múzeum otvorené pre verejnosť. Okrem toho v roku 1904 postavil neďaleko hradu secesné mauzóleum. Od roku 1945 je Krásna Hôrka majetkom štátu.