Kořeny Medlova sahají hluboko do středověku. Za nejstarší písemnou zmínku je považován název „Medli Ugezdec“ v listině olomouckého biskupa Jindřicha Zdíka z první poloviny 12. století. Ves byla původně česká, v průběhu staletí se několikrát poněmčila a po druhé světové válce se opět stala převážně českou obcí.
Medlov ležel na obchodní stezce mezi Mohelnicí a Uničovem. Tato cesta nesloužila jen kupcům; vedla také k hradu Úsov, centru panství, kam poddaní docházeli se svými povinnostmi. V roce 1391 získali obyvatelé významné privilegium na tzv. odúmrť, které jim umožnilo lépe nakládat s vlastním majetkem a motivovalo je k zvelebování hospodářství.
Zásadním milníkem bylo také privilegium krále Vladislava II. Jagellonského z roku 1502, jímž Medlov získal právo používat vlastní pečeť a znak. V červeném štítě jsou vyobrazeny části pluhu – radlice a krojidlo – symbolizující zemědělský charakter obce. Znak se objevuje nejen na historických pečetích, ale také v kostele, kde je dochovaná jeho podoba z roku 1520 doplněná dvěma supími hlavami z erbu pánů z Vlašimi.