Герцога Апулийского часто недооценивали, ему обычно удавалось быстро развеять это заблуждение. Первой неожиданностью для барийцев стало появление у их берегов нормандских кораблей. Сицилийский опыт и в особенности неудачная попытка осады Палермо, предпринятая четырьмя годами раньше, убедили Роберта в необходимости и важности поддержки с моря. Сразу по возвращении он стал собирать корабли по всему Адриатическому побережью, и, хотя сначала флот предназначался скорее для борьбы против сарацин, нежели против греков, теперь Роберт привел все имевшиеся в его распоряжении суда в Бари. Тогда его морские силы не шли ни в какое сравнение с тем флотом, которым он обладал через несколько лет, но они сделали свое дело. Выстроив корабли в ряд и соединив их большой железной цепью, скованной специально для этого случая, Роберт обнес заграждениями весь мыс, на котором стоял город. Корабли, располагавшиеся на концах шеренги, были пришвартованы к хорошо защищенному пирсу, таким образом воины могли взойти на эти корабли и, переходя с судна на судно, добраться до того звена в цепочке, на которое будет направлена атака. Тем временем нормандская армия расположилась вдоль стен и перекрыла все подходы к городу с суши. К немалому удивлению его жителей, город оказался в кольце. Никакие насмешки больше не доносились с крепостных стен. 5 августа 1068 г. началась знаменитая осада Бари.
Она была долгой и дорого обошлась обеим сторонам. Греческий военачальник Византий сумел каким-то образом проскользнуть через ряды нормандцев и спастись от преследования; он благополучно добрался до Константинополя и убедил императрицу организовать спасательную экспедицию. (Ему повезло, что он прибыл уже после отъезда императора в Малую Азию: Роман, которого нормандцы, находившиеся на расстоянии в семьсот миль, заботили гораздо меньше, чем сельджукские орды у дверей, запросто мог отказать.) В начале 1069 г. греческие корабли появились в Адриатике. Нормандцы их перехватили и после первых неудачных попыток все же потопили двенадцать грузовых судов у Монополи; но кордон вокруг Бари не выдержал прямого удара, и несколько кораблей, включая тот, на котором плыл Византий вместе с новым катапаном и выдающимся военачальником Стефаном Патераном, прорвались в гавань, доставив оружие и припасы осажденному городу. Случившееся не только задело гордость нормандцев, но и порождало мрачные сомнения; ведь если они не в состоянии обеспечить полную блокаду, Бари может стоять вечно. Но герцог Апулийский не отступал. Осада продолжалась весь 1069 г. и, несмотря на убийство Византия в июле, весь 1070 г. тоже. Однажды осенью Патеран, забеспокоившись из-за угрозы голода, а также из-за того, что некоторые горожане стали открыто выражать свои пронормандские настроения, задумал, в свою очередь, убить Гвискара. Однажды вечером, когда Роберт обедал в лачуге из бревен и прутьев, которую построили для него у крепостной стены, наемный убийца подкрался и метнул в него отравленное копье через щель в стене. Если верить Вильгельму из Апулии, только жестокая простуда, донимавшая Роберта, которая заставила его в этот самый момент наклонить голову под стол, чтобы откашляться, спасла ему жизнь. Благодаря счастливому стечению обстоятельств он остался цел и невредим, но на следующее утро нормандцы начали строить здание из камня, без щелей, чтобы в дальнейшем уберечь своего предводителя от подобных инцидентов.
Зима 1070/71 г. была тяжелой и для осажденных, и для осаждающих – физически и морально. Патовая ситуация сохранялась уже два с половиной года без всякой надежды на скорые перемены. Город получил помощь и мог получить ее вновь; но сейчас съестных припасов оставалось мало. Патеран решил обратиться к Византии с последним отчаянным призывом. Турецкая угроза была, как он знал, все еще велика. Но сам он пользовался некоторым авторитетом в столице, и была надежда, что он сумеет убедить императора Романа, добившегося определенных успехов в последней кампании, выделить часть своих ресурсов для спасения Апулии, пока еще имелась возможность это сделать. Нормандская морская блокада вновь оказалась недейственной: вскоре Патеран спешил в Константинополь.