Mezilesí bylo založeno na staré obchodní cestě, která vedla z Vratislavi přes město Kladsko do Brna a Vídně. Kníže Břetislav I. zde k ochraně této cesty vystavěl hradiště. Roku 1294 je doložena existence Mezilesí jako města – král Václav II. jej daroval s okolním panstvím řádu cisterciáků jako české léno s tím, že má zůstat „na věčné časy“ součástí Českého království. Roku 1428 bylo Mezilesí zničeno husity. Roku 1491 bylo znovupostaveno. Za třicetileté války bylo Mezilesí opět těžce poničeno. Roku 1627 a 1643 bylo vypáleno Švédy.
Spolu s celým Kladskem bylo Mezilesí roku 1742 postoupeno Prusku a následně se stalo součástí Německa. Roku 1875 byla zprovozněna železniční trať Vratislav–Mezilesí–Praha–Vídeň.
Do roku 1945 tvořili většinu obyvatelstva Mezilesí Němci. Po druhé světové válce oblast nárokovalo Československo. Nakonec byla ale celá sporná oblast přičleněna k Polsku. Dnes Mezilesí obývají Poláci, přistěhovalí především ze středního a východního Polska.
Dnes je Mezilesí železničním hraničním přechodem mezi Polskem a Českou republikou, na trati Vratislav - Kladsko - Lichkov.