A környező területet III. Béla magyar király1183-ban a szentgotthárdi monostornak adományozta. Az első erődítményt a templomosok építették a keresztes háborúk idején. 1208-ban Vasvári András gróf hűbérbirtoka lett, ő jelentősen kibővítette a várat. Ekkor említik először írásban is "Lyndwa" alakban. Valószínűleg már ekkor állt a régi templom is, melyet Ottokár cseh katonái pusztítottak el. 1269 és 1275 között II. Ottokár cseh király birtokában volt, majd a Gutkeled nembeli Amadéé, a Felsőlendvaiak őséé lett. Amadé Miklós szlavóniai bán 1367-ben csatát vívott Hodos mellett és megszerezte a muraszombati uradalmat is. Az Amadé család család kihalása után, 1365-ben a vár birtokcserével a Széchyek tulajdonába került.
Felsőlendva település a középkori vár körül alakult ki. 1365-ben "Waraliafolu" néven említik abban az oklevélben, melyben Felsőlendva várát a hozzátartozó 73 faluval I. Lajos magyar király elcseréli Széchy Miklóssal Éleskő és Miskolc uradalmáért, valamint a Szent Péter és Pál apostolok tiszteletére létesült tapolcai apátság kegyuraságáért. 1478-ban már mezőváros, hiszen "opidum Lyndwa" alakban említik, majd 1499 ismét "oppidum Felsewlyndwa" néven szerepel.
Felsőlendva plébániáját még 1400 előtt alapították. A Széchy család a 16. században jelentősen hozzájárult a protestantizmus elterjesztéséhez a vidéken. Felsőlendva temploma is protestáns kézbe került. A katolikusok csak 1660-ban alapították újra plébániájukat. Filiái Kuzma, Motolyád, Ottóháza, Radófa, Szentmátyás, Tiborfa, Vaskorpád, Vaskovácsi, Vidorlak és Völgyköz voltak. A várat birtokosai rendszeresen bővítették, fejlesztették. Ennek ellenére a 16. és a 17. században többször is elfoglalták. 1515-ben és 1549-ben a felkelő parasztok, 1605-ben és 1616-ban a Habsburg-ellenes felkelők, 1685-ben és 1688-ban pedig török fosztotta ki. Utoljára 1704-ben a kurucok foglalták el. 1684-ben a Széchy család is kihalt férfiágon, és a birtok a Batthyányiaké, majd a Szapáryaké, illetve a Széchenyi családé lett, akik az első világháború végéig birtokolták.
A település mezővárosi rangban a 19. században a Tótsági járás egyik nagytelepülése volt. 1890-ben már hivatalos neve is Felsőlendva, ekkor alapították a helyi önkéntes tűzoltó egyletet is.
1952-ben hivatalos nevét Gradra változtatták az addigi Gornja Lendava helyett.
Népesség
1890-ben 809 lakost számláltak a településen, közülük 660 szlovén, 121 német, 23 magyar és 2 egyéb nemzetiségű volt.
1910-ben 1025, többségben szlovén lakosa volt, jelentős magyar kisebbséggel. 1921-ben a népszámlálás szerint 1024 szlovén, 20 magyar, 20 német lakta, közülük 976 katolikus, 82 evangélikus volt. 1931-ben 1020 lakost számláltak itt. 1961-ben 937 lakosa volt. 1971-ben 920 lakosa, 197 háza, 221 háztartása volt, lakói főként mezőgazdaságból éltek.
2002-ben a községnek 2302, Felsőlendvának külön 686 lakosa volt.
Nevezetességei
A felsőlendvai vár Szlovénia legnagyobb várépülete. Mai ötszögű formáját a 17. és 18. században kapta, amikor a kényelmetlen középkori épületet barokk stílusú várkastéllyá építették át. Ebből az időszakból származik a vár kápolnája is, tornya 1751-ben épült. A vár védelmi céljait szolgálta a sziklába ásott várkút. Pincéjében hatalmas börtön volt. Számos értékes fával beültetett nagy park övezte, ahol két halastavat is létesítettek. A két világháború között az akkor még jó állapotban lévő vár Hartner Géza muraszombati nagybirtokos tulajdonában volt. A második világháború során a vár súlyos sérüléseket szenvedett és teljesen kifosztották. A háború után szovjet csapatokat szállásoltak el benne, majd köztulajdonba vették. Egy darabig hivatalokat helyzetek el benne, néhány család is beleköltözött, de egyre jobban leromlott az állapota. A hetvenes évek elejére részben felújították, házasságkötő termet és múzeumot berendeztek be benne. A felújítási munkák 2008-ban is folytatódnak EU-s támogatással.
A Nagyboldogasszony tiszteletére szentelt római katolikus temploma 14. századigótikus épület, de legrégibb részei még román stílusban valószínűleg 1275 körül épültek. A 14. században épült a szentély és a templomhajó, eredeti gótikus mennyezetét 1660-ban átépítették. 1690-ben fatornyot építettek hozzá. A mai 35 méter magas harangtorony 1729-ben épült. 1781-ben a templomot teljesen megújították. Főoltára 1778-ban készült, Janez Klein szobrászművész alkotása, rajta áll az 1510-ben készített Mária a Kisjézussal szobor. Mellette kétoldalt Keresztelő Szent János és Szent József aranyozott szobrai láthatók.