Prvá písomná zmienka o obci pochádza z roku 1270.
V roku 2020 oslávila Kamenica 750. výročie od prvej zmienky.
 
V listine z roku 1270 kráľ Štefan V. (1270 – 1272) daroval za zásluhy v bojoch proti kráľovi Belovi IV. (1235 – 1270) synom Detrika z Kércsu (Abovská stolica), pôvodom z rodu Apc (Detmarovi, Detborovi, Detkovi, Šimonovi, Herbordovi, Mikovi a Langovi) a ich spoločníkom (Števkovi, synovi Mohola, Jánovi, synovi Mikuláša a Petrovi a Eugenovi, synom Jána) kráľovský poľovnícky revír siahajúci až k poľským hraniciam, nazývaný Bachamezey (Bačovo pole) a Torkueley. Donácia sa týkala územia dnešných dedín Pusté Pole a Kamenica. Hrad v tom čase ešte nestál, postavili ho až na prelome 13./ 14. storočia a prvá písomná zmienka o ňom je z roku 1306.
Názov obce TORKUELEY znamená POD HOLÝMI SKALAMI
(názov je z maďarského tor - tar = holý, ku - kő = kameň, eley - pod)
(Informácie: M. Tihányiová - T. Janura: Dejiny hradu Kamenica. IN Michaela Haviarová a kol.: Hrad Kamenica – tajomný hrad Čergova, Obec Kamenica, 2016.)