Ekspansja na południe Po objęciu władzy Stefan Milutin podjął ekspansję na południe w stronę Macedonii, którą Michał VIII Paleolog, jeszcze jako dowódca bizantyński, zdobył w 1259 roku częściowo na Epirze, a częściowo na Serbii (w 1258 roku Stefan Urosz I przejściowo opanował bowiem Skopje, Prilep i Kiczewo). W 1282 i 1283 Milutin podbił północną Macedonię ze Skopjem, lecz dopiero po trwającej wiele lat wojnie w 1299 roku uzyskał ostatecznie od cesarza Andronika II jako wiano córki cesarskiej Symonidy Paleologiny, która została czwartą żoną Milutina. W 1308 Stefan Milutin ustalił przebieg granicy z Cesarstwem zajmując ziemie debarskie do Mat, ziemię kiczewską do granic Ochrydu, prilepską do miasta Prilep i do granic Proseka, a w końcu ziemię owczenską po miasto Sztip. Domagał się też przyznania mu Sztipu, który zdobył już wcześniej, ale bez powodzenia. Mimo ustaleń granica była stale naruszana, a jej okolice niespokojne.