Nazwa Nazwa Miedzna najprawdopodobniej pochodzi od słów mied, miedza, oznaczających „kraj, krawędź, granicę”. Jej pierwotna nazwa – Międzylesie, związana jest z lokacją miejscowości na skraju lasów, które stanowiąc odnogę Puszczy Białej wychodziły na południe, za linię Bugu.
Historia mały|lewo|Ruiny dworu obronnego w miejscu starszego grodziska Miedzna pojawiła się w źródłach po raz pierwszy w 1441 roku. Pierwszymi właścicielami miejscowości i okolicznych wsi byli Karscy. Po nich dobra miedzeńskie przejęli Wodyńscy, następnie Butlerowie i Kuczyńscy. Miedzna już wówczas była wsią parafialną. Świątynia katolicka istniała tu w 1470 roku i została ufundowana przez Wodyńskich. Kościół nosił tytuł Zwiastowania Najświętszej Marii Pannie.
W 1522 roku Jan Wodyński, ówczesny dziedzic dóbr międzyleskich, otrzymał od Zygmunta Starego przywilej lokacji miasta. Wznowienie przywileju nastąpiło w 1531 roku. Wówczas na gruntach wsi Międzylesie w pobliżu grodziska założono miasto na prawie magdeburskim z prawem wzniesienia ratusza i kamer. Od połowy XVI wieku Jan Wodyński przeszedł na kalwinizm. Miedzna wówczas stała się silnym ośrodkiem protestantyzmu. Parafią kierowali ministrowie protestanccy. Stan taki trwał do XVII wieku. W 1580 roku miasto liczyło 600 mieszkańców.