W księdze łacińskiej Liber fundationis episcopatus Vratislaviensis () spisanej za czasów biskupa Henryka z Wierzbna w latach 1295–1305 miejscowość wymieniona jest w zlatynizowanej formie Meczibor. Kronika ta wymienia również wsie, które w procesach urbanizacyjnych zostały wchłonięte przez miasto i stanowią jego części bądź dzielnice jak np. Zielonka w formie GelonaLiber fundationis episcopatus Vratislaviensis onlineH. Markgraf, J. W. Schulte, "Codex Diplomaticus Silesiae T.14 Liber Fundationis Episcopatus Vratislaviensis", Breslau 1889. W roku 1613 śląski regionalista i historyk Mikołaj Henel z Prudnika wymienił miejscowość w swoim dziele o geografii Śląska pt. Silesiographia podając jej łacińską nazwę: Medcziboria.
Kolejne podają często różne wersje nazwy miasta: w roku 1310 Mechobocz, w 1376 Meczebor, w 1637 Medzibor. W 1886 r., na fali rosnących nastrojów nacjonalistycznych, zastąpiono posiadającą polskie korzenie nazwę Medzibor niemiecką formą Neumittewalde.