První písemná zmínka o Leštině pochází z roku 1392, i když obec jistě existovala již dříve. Místní části obce Zálavčí patří o 21 let starší zápis z roku 1371.

Jméno Leština je odvozováno od "místa s lískovými keři", tj. leščiny. Poloha obce byla dobře zvolena, neboť spojovala výhodu úrodných rolí ve střední nadmořské výšce s výhodou dobré komunikační polohy na cestách od Zábřeha k Úsovu, opačným směrem k Lesnici a dále na sever do jesenického podhůří. Obec leží rovněž na významném přechodu přes řeku Moravu, na jejímž mostě bylo již v 16. století vybíráno mýto. Uvádí se, že nejstarší dějiny obce jsou spojeny s nedalekým Dubickem, ale již koncem 14. století patří Leština k Zábřehu.