Пока правители на Далматинском побережье боролись между собой за церковную юрисдикцию, по соседству появились норманны. Они завладели Южной Италией (областями Калабрия, Аггулия, Бари), вытеснив оттуда Византию. Время от времени они проникали на противоположный берег Адриатики; папы и византийские императоры, а также соперничавшие друг с другом претенденты на папский престол часто использовали их в качестве политического орудия. Наиболее желанными для норманнов были византийские территории: они нападали на Драч, откуда начиналась древняя античная дорога via Egnatia, которая вела в Салоники.
Между тем давление Византии на Дуклю ослабло, и не только из-за отступления из Италии, но и в силу затяжной борьбы за императорский престол (1078–1081), а также в силу миролюбивой политики ставшего самостоятельным наместника в Драче. С норманнами, новыми хозяевами противоположного берега Адриатики, Михаил установил тесные контакты. В апреле 1081 г. он женил своего сына Бодина на дочери одного из главных приверженцев норманнов в Бари. И тем не менее, когда на византийский престол взошел император Алексий I Комнин (1081–1118), Михаил и его сын Бодин оказались в числе сторонников Византии, вместе с Венецией и Албанией. Бодин постоянно совершал нападения на норманнов, однако в решающей битве сними 18 октября 1081 г. участия не принял, что повлекло за собой поражение византийской армии и падение Драча.
После захвата Драча норманны дошли до Охрида и Скопле, но уже в следующем году временно прекратили свой поход, а в 1085 г. были окончательно остановлены. Византийская армия во главе с императором Алексием I, энергичным и талантливым военачальником, вытеснила норманнов с захваченных ими территорий и вернула Драч, а также Дубровник (последний сдался норманнам в 1081 г.). Тем временем Михаил умер, и власть полностью перешла к его сыну Бодину. В соседнем Драче тогда правил наместник Иоанн Дука, родственник императора и тоже энергичный и талантливый полководец. Дука постоянно нападал на соседей и даже отвоевал несколько городов у великого жупана Вукана. В одной из стычек, предположительно между 1085 и 1090 гг., Дука разбил войско Бодина, а его самого взял в плен, но затем с согласия императора оставил на княжеском престоле. Другими сведениями о конфликтах Бодина с Византией мы не располагаем.
Бодин был также втянут в борьбу городов за сферы церковного влияния, но в отличие от отца, отстаивавшего права Дубровника, он энергично поддерживал Бар, находившийся, судя по всему, под его властью. В 1089 г., обойдя Урбана II, законного наследника Григория VII и впоследствии главу католической церкви, Бодин обратился к ставленнику немецкого короля Клименту III. Ему удалось получить от антипапы буллу, согласно которой епископ Бара получал сан архиепископа, а Бар, соответственно, наделялся статусом архиепископства, имевшего церковную юрисдикцию над епископствами Дукли, Бара, Котора, Улциня, Свача, Дриваста, Пилота, а также над Сербией, Боснией и Травунией (три последние раньше находились под юрисдикцией Дубровника).
