Obec vznikla na prelome 13. – 14. storočia. Najstaršia písomná zmienka o dedine Klátov v podobe „Vyfolu sev nemutfolu“ v preklade „Nová Ves“ pochádza z roku 1317. Pôvodnými obyvateľmi Vyšného Klátova boli počas celého stredoveku Nemci. Hoci v 16. a 17. storočí do obce prichádzali Slováci, stále boli v menšine. Prevahu nadobudli až počas 18. storočia. Prvým známym feudálnym vlastníkom Klátova bol istý pán Hannus, po ňom zemania z Bašky a od roku 1382 mesto Košice. Poddanským majetkom Košíc zostala obec až do 19. storočia. Svedčí o tom aj jej maďarský názov „Felsotokes“, z ktorého bol v 20. storočí odvodený slovenský názov. Maďarské slovo „toke“ v preklade znamená „peň“ , „klát“. Obec počas svojho historického vývoja dostala rôzne názvy: „Superior Turas - Tukes“, „Fel-Teukes“, „Superior Beckseyffen“, „Wiszneho Tekuskeho“, „Wisny Tokes“, „Vyšny Tejkeš“ po maďarsky „Felsotokes“.