Вскоре внимание Милютина было отвлечено событиями, происходившими в Болгарии. После царя Константина на болгарский престол был избран Григорий Тертерий (1280—1292), при котором Болгария подверглась нападению татар; последние свергли Тертерия, возвели на престол некоего Смильцу (1292 г.) и поручили виддинскому наместнику Шишану начать войну с Сербией. Шишман вторгся в Сербию и, разоряя все по пути, дошел до Ужицы, где был остановлен и разбит наголову архиепископом Савою.
Тем временем Милютин вместе с братом Драгутиным, окончив приготовления, перенесли войну в Болгарию и, заняв виддинский округ, осадили Виддин. Шишман просил мира, который и был заключен, причем сын Шишмана Михаил женился на дочери Милютина Неде.
Недовольный таким исходом дела, хан Негой грозил возобновить войну, но после долгих переговоров отстал от своего намерения, причем Милютин должен был дать ему в заложники своего сына Стефана. Последний, однако, недолго оставался в плену; он женился на дочери болгарского царя Смильцы и, возвратившись в Сербию, получил от своего отца в удел Зету, в которой и поселился (1294 г.).