Некогаш Лешок бил град и се викал Легенград, се наоѓал на калето и бил заграден со висок ѕид и никој не можел да влезе и да го заземе. Турците пробале да го заземат, ама никако не можеле. Тогаш една жена им рекла: „Ако сакате да го заземете градот, идите откај планината“.
Турската војска отишла откај планината, го нападнала градот и го зазеле градот. Љуѓете што биле во градот избегале и запалиле огин кај што е денешното село Варвара. Кога виделе Турците оѓин извикале: „вар, вар“ што значи на турски „има, има“.
Жената што го издала градот, била проколната непросто да и биде до век. Од неа настанало селото Непроштено, а името е од зборот непросто.
Така избеганите го создале селото Варвара, а името го добило по турскиот збор вар. Според една легенда денешното име селото Лешок го добило по зборот леш што во преносна смисла се однесува на целосно разурнат град.
Според друга легенда името Лешок го добил името по дрвото може да се потврди и по тоа што денес постојат два топоними со име леске. Едниот топоним е на влезот во селото, а другиот е над селото, над местото Солишта од левата страна на Лешочка река.
Во предание кај жителите на Лешок се пренесува легендата за градското златно богатстство на градот.
Когај Турците го разурнале градот не можеле да го пронајдат златото затоа што тоа се наоѓало внатре во калето. Него го чувал еден голем смок кој еднаш годишно излагувал да се напие вода во реката што тече покрај калето. Когај ќе излезе да пие вода, опашката му е у дупката, а главата у Лешочка река.
Историски се знае дека Лешок бил град, меѓутоа него го разурнал Стеван Немања во 1189 година, а пак Турците Полог го освоиле кон крајот на 14 век.
Раскажал, Тоде Дамјановски-Гуде, забележал Илија Пертрушевски, Лешок,Живко Трпко Спироски, Тоде Дамјановски-Гуде .Забележал, Митко Спироски,Илија Петрушевски
