Zprávy o hradu jsou po většinu jeho historie velmi kusé. Přimda je obvykle spojována s blíže neznámým hradem, který měli podle Kosmovy kroniky roku 1121 vystavět Němci na české straně hraničního lesa a který jim vzápětí český kníže Vladislav I. vzal. Souvislost této zprávy z Kosmovy kroniky s Přimdou není ale prokázána, stejně jako v některé literatuře uváděná hypotéza, že uvedeným Němcem a zakladatelem hradu byl bavorský Děpold II. z Vohburku. Pravděpodobně byla Přimda ve své kamenné podobě založena českým knížetem k ochraně hranic.

První zmínka o hradu pochází už z roku 1126, kdy hrad nechal přestavět (společně s Tachovem a Zhořelcem) kníže Soběslav I.

Od počátku plnila Přimda i úlohu státního vězení. V průběhu neklidných dob 12. století zde byl dvakrát po řadu let vězněn budoucí kníže Soběslav II. svým bratrancem, knížetem Vladislavem II. Z prvého věznění byl Soběslav osvobozen svými přívrženci, kteří hrad přepadli, zabili purkrabího a shodili ho do vězení. Dalšího purkrabího Přimdy nechal Soběslav potrestat i po svém druhém osvobození, kdy se stal knížetem.

V roce 1249 si vyzkoušel vězení na Přimdě i Přemysl (budoucí král Přemysl Otakar II.) po neúspěchu vzpoury proti svému otci a králi Václavu I.

V průběhu 14. století se hrad Přimda stal centrem asi 15 chodských vesnic, jejichž obyvatelé byli povinni strážní službou na hranici. Dále byl i centrem přimdeckých manství, jejichž držitelé – manové – byli povinni vojenskou službou pro hrad. Zároveň se zde na jedné z větví norimberské cesty vybíralo clo.

Za Jana Lucemburského byla Přimda výměnou za finanční hotovost zastavena (dána do držení) šlechtě.

V roce 1336, v době sporů Jana Lucemburského s císařem Ludvíkem IV. Bavorským, byl hrad přepaden německým vojskem, obléhatelé překonali vnější opevnění, museli však ustoupit po zapálení dřevěných částí hradeb posádkou hradu.

Karel IV. v rámci snah o upevnění panovnické moci a jejích opor - královských hradů - Přimdu vyplatil a ta se zařadila mezi hrady, které musí zůstat králi. V následující době však byla Přimda opět zastavována.

V roce 1406 přešla Přimda do rukou Boreše z Rýzmburka. Borešem dosazený správce Tista však zřejmě se souhlasem svého pána loupežemi sužoval široké okolí (výpravy zasáhly až na Berounsko). V roce 1416 královské vojsko zajalo v hospodě v městečku skupinu 30 hradních ozbrojenců, kteří byli následně v Praze oběšeni. K potlačení odporu Rýzmburků proti králi vedla až výprava v roce 1418, kdy byl hrad oblehnut královským vojskem a jeho posádka se vzdala. Následně byl hrad Rýzmburkům odebrán.

V husitském období, kdy jí držel Zikmundův straník Jindřich Žito z Jivjan, patřila Přimda k spolehlivým oporám katolické strany. Roku 1429 byla znovu krátce a neúspěšně obléhána, tentokrát husitským vojskem, které alespoň zničilo městečko pod hradem.

V roce 1454 získali Přimdu do zástavního držení Švamberkové. V jejich rukách pak Přimda zůstala až do roku 1592. Bratři Adam a Jindřich ze Švamberka si v roce 1548 panství i hrad rozdělili, přičemž Adamovi připadl tzv. horní hrad, zatímco Jindřichovi hrad dolní (horní a dolní hrad byly odděleny podélným skalním hřebenem). Za Švamberků v 16. století Přimda chátrala a ani dílčí opravy a některé nové hospodářské budovy stav hradu nezlepšily. Došlo i k bourání některých částí hradu. Chodové, zajišťující ostrahu hranic, si panovníkovi stěžovali na zchátralost hradu a „tunelování“ financí, určených na jeho opravy.

Po smrti obou bratří Adama i Jindřicha získal roku 1592 hrad s panstvím Rudolf II. a raději tento majetek rozprodal. Hrad následně koupila obec, ale již roku 1601 ho musela opět prodat.

V roce 1609 byl již hrad uváděn jako pustý, zbořený a opuštěný.

Následně zřícenina několikrát změnila majitele, až se roku 1675 dostala do majetku hraběte Jana Václava Novohradského z Kolovrat, který centrem panství učinil nedaleké Velké Dvorce. V roce 1711 do obytné věže uhodil blesk a následně se zbortila její jihozápadní část až do úrovně přízemí.