Vyšná Kamenica je v porovnaní s ostatnými susednými dedinami najmladšou obcou. Prvýkrát sa spomína v roku 1420, teda na začiatku 15. storočia. To, že je obcou najmladšou, môžeme, podľa dostupných historických materiálov, vysvetliť snáď tým, že na konci 13. storočia existovala severnejšie od Vyšnej Kamenice dedina Púch. Ležala asi 3 km severne od terajšej obce. Posledná správa o dedine Púch pochádza z roku 1370 a hovorí sa v nej, že je ľudnatou dedinou s 12 usadlosťami. Na rozhraní 14. a 15. storočia sa títo obyvatelia z neznámych dôvodov presťahovali asi 3 km nižšie do údolia Kamenického potoka a založili novú dedinu.