Королевский кортеж отравлялся из Регенсбурга 18 февраля 996 года. Под пение псалмов пешие солдаты и конница проследовали через весь город. Герцог Генрих IV сопровождал короля в окружении мощного эскорта баварских рыцарей. Путешествие проходило через Иннталь, перевал Бреннер (Альпы) и Эйзак и Эчталь. Только южнее Тринта караван покинул Баварию, владения герцога Генриха, которые тогда распространялись через Альпы намного южнее.
Известие о приближении короля Оттона III достигло рубежей Италии намного быстрее его солдат. Первый лагерь был разбит рядом с Вероной после тяжелейшего перехода через Бреннер, где в тот момент еще лежал снег и стояла зима. Воины расположились в палатках, расставленных прямо на примыкающей к королевской резиденции лагерной площади, а привилегированные господа заняли саму резиденцию и стоящий неподалеку монастырь Сан-Зено. Три королевские семьи укрылись за городскими стенами Вероны, охраняемые постоянно расквартированным здесь имперским гарнизоном.
Герцог Генрих находился где-то поблизости, но не постоянно рядом с королем. Оттон III предпочитал интимные беседы с глазу на глаз, частенько уединяясь с друзьями или интересными собеседниками. А между герцогом Генрихом IV Баварским и королем Оттоном III сложились и развивались особо доверительные отношения, ставшие за годы правления последнего совсем близкими. Участие герцога Генриха в переговорах и в решении возникающих проблем приносило ему знания и дополнительный опыт, ставшие впоследствии источником важнейших знаний в политических вопросах. Конечно, не последнюю роль в становлении его как политика сыграло и знакомство с некоторыми представителями дворянства, людьми искусства, науки, церкви.
Герцог в свите короля исполнял обязанности советника по военным вопросам, поскольку военного опыта у совсем еще молодого короля быть не могло. Да и мощь баварской части королевского войска была наибольшей среди всех представленных в походе герцогств. Руководство походом требовало, таким образом, постоянного присутствия герцога в королевском шатре.
В Верону прибыли итальянские солдаты, усилившие войско Оттона III. Речь здесь идет о группировке из Аквилеи и Комо, а также о подразделениях герцога Оттона Каринтского. Впервые герцог Генрих получил представление о том, насколько взрывоопасны отношения между простым народом и властями предержащими в итальянских городах. Из-за превышения власти некоторыми из солдат по отношению к простому народу почти перед воротами резиденции вспыхнули беспорядки, при устранении которых погибли несколько высокопоставленных господ. Только выдержка позволила Оттону III избежать кровавой бойни.