Из Петербурга фельдмаршал выехал в Европу в конце февраля. В Вильне Суворов встретился с фанагорийцами, испытанные гренадеры (история сохранила фамилию Кабанова) просили его взять их с собою в Италию. Суворов обещал просить о том государя, но тщетно: дорога Фанагорийского полка не лежала через Италию… Им предстояло под командованием генерала И.И. Германа воевать в составе экспедиционного корпуса в Голландии. Но то был бесславный поход, окончившийся несколькими поражениями — в том числе в большом сражении при Бергене и пленением самого Германа, которого Павел в гневе уволит из армии. По иронии истории, Германа, который должен был приглядывать за Суворовым в Итальянском походе, Россия выменивала на пленных французских генералов Периньона и Груши.
14 марта 1799 г. Суворов прибыл в Вену, встречавшую его как героя. Въезжая в Вену, по легенде, Суворов изо всех сил кричал: «Да здравствует Иосиф! Да здравствует Иосиф!» Когда же его прервали и объяснили, что императора зовут Францем, старик изобразил удивление: «Видит Бог, что я этого не знал». Стремительному фельдмаршалу было не до мелочей.
И всё-таки ему пришлось потратить драгоценное время на аудиенцию у императора Франца, на светские беседы с императрицей и французскими принцессами… Приёмов могло бы быть значительно больше, но Суворов отказался от них, сославшись на Великий пост. Зато встретился со старыми боевыми друзьями — принцем Кобургским и бароном Карачаем. Последнего, пребывавшего к тому времени в отставке, Суворов уговорил вернуться в армию и снова сражаться рядом с русскими, как при Путне, Фокшанах и Рымнике. Неоднократно Суворов встречался с русским посланником графом Андреем Кирилловичем Разумовским, с которым он считал возможным говорить откровенно на самые мудрёные темы. Суворов знал, что Разумовский был деятельным посредником между союзниками и Павлом и сыграл чуть ли не первую скрипку в назначении Суворова главнокомандующим. Заслуги чрезвычайного посла в создании коалиции Павел Петрович щедро оценил орденом Андрея Первозванного. Рядом с Разумовским, по распоряжению Павла, работал Степан Алексеевич Колычев — тайный советник при русском посольстве в Вене. С ним Суворов также сошёлся, нашёл общий язык, упражняясь в умении вести многозначительные политические беседы.
Ко времени пребывания Суворова в Вене относится любопытная легенда: Суворова-де пригласили на оперу великого Моцарта (назовём без особого умысла, к примеру, «Волшебную флейту»). Иногда рассказывают: «Дирижировал сам композитор!» На самом деле Моцарт до 1799-го не дожил. После представления Суворов высказался: «Хорошо играют. Но наш полковой оркестр звучал и получше!» Пробыл он в Вене 10 дней и на прощание получил от императора Франца инструкции по ведению первого этапа кампании. Речь шла о защите австрийских владений от французов с постоянной оглядкой на гофкригсрат. Главная задача — оттеснение французов подалее от австрийских владений. Суворов не мог согласиться с такими планами, не для этого он оставил Кончанское. Свою стратегию он выработал ещё в Кончанском — она запечатлена в плане, продиктованном И.И. Прево-де-Люмиану. Новая стратегия, предполагавшая разгром неприятеля. Но — то ли из легкомысленности, то ли из высшей мудрости — не соглашаясь с австрийцами, он не настоял на документальном утверждении своих более широких планов. Что ж, принцип «главное — ввязаться в драку» при запутанных обстоятельствах иногда бывает верным, но в Вене были заложены основы будущих противоречий Суворова и Тугута, России и Австрии. Суворов направился по маршруту Вена — Верона. На пути в Верону, в Виченце, к Суворову присоединился генерал-квартирмейстер армии маркиз Шателер. Он принялся со схемами и картами в руках рассказывать о расположении войск. Когда же спросил Суворова о планах кампании — услышал в ответ рассеянное «Штыки, штыки…». Суворова беспокоило невеликое умение австрийцев побеждать штыковыми атаками, а делиться более подробными планами с Шателером он не считал нужным. К тому же не нова истина: «Война план покажет». Когда же австрийцы представили Суворову свой план кампании, итогом которой должно было стать оттеснение французов к реке Адде, Суворов сказал:
— Кампания начнется на Адде, а кончится, где Богу будет угодно…
В Вероне его приветствовали генералы и войска. Он перебросился словами с Багратионом, Розенбергом, Милорадовичем. Розенберга испытал неожиданным приказом: «Дайте мне два полчка пехоты и два полчка казаков!» Генерал, не знавший повадок Суворова, ответил вполне серьёзно, что вся армия в распоряжении командующего. На следующий день Суворов повторил свою странную просьбу, Розенберг снова не сумел ответить остроумно. Выручил Багратион: «Мой полк готов, ваше сиятельство». Суворов был вполне доволен таким находчивым ответом: Багратион прочувствовал, что Суворов говорит о подготовке авангарда. Вопросы «на находчивость» не были пустой блажью фельдмаршала. Таким образом Суворов воспитывал в генералах и солдатах дух смелой инициативы. У Суворова воюют личности, а не механизмы, и он любил, чтобы личность проявлялась в гротескном виде.
По обыкновению, он много общался с нижними чинами, вспоминая о прошлых сражениях, пошучивая, поощряя молодых… В первые дни Итальянского похода проявилась особенность Суворова, которую ценил Денис Давыдов: «Прежние полководцы, вступая в командование войсками, обращались к войскам с пышными, непонятными для них речами. Суворов предпочёл жить среди войска и вполне его изучил; его добродушие, доходившее до простодушия, его причуды в народном духе привлекали к нему солдат. Он говорил с ними в походах и в лагере их наречием. Вместо огромных штабов он окружал себя людьми простыми, так, например, Тищенкой, Ставраковым». Вот вам и разгадка, почему именно Суворова армейская и крестьянская молва прочно выделила из ряда русских полководцев, прославленных громкими победами.
Новую главную квартиру устроили в Валеджио. В марше на Валеджио авангардом командовал князь, генерал-майор Багратион, который прославится авангардными боями в течение всей кампании. В корпусе Багратиона шёл вверенный грузинскому князю 6-й егерский полк, сводный гренадерский батальон неустрашимого подполковника Ломоносова и полк казаков майора Поздеева. Суворовская инструкция авангарду стала принципом Багратиона на всю кампанию: «Голова хвоста не ждёт. Как снег на голову». Суворовский солдат, Илья Осипович Попадичев, вспоминал уже в глубокой старости о том марше: «Отсюда с Багратионом мы сделали три перехода вольно, при нас ехал Суворов. Тут вдруг последовал от него приказ, чтобы штыки были у всех востры. Для чего это он велит вострить штыки, думали мы, потому что они у нас были остры, как шилья. После уж узнали, что Суворов, объезжая полки, попробовал рукой штык у одного солдата и нашёл его тупым — вот и отдал приказ, чтобы все навострили штыки». Прелюдия сражений прошла под знаком внимания к штыку.
Суворов стремился «взорвать ситуацию» в Италии. Его не устраивали медлительные действия французов в марте и начале апреля, когда многотысячная австрийская армия медлительно двигалась по берегам реки Минчо, позволяя французам действовать в Италии.
В Валеджио, ожидая отстававшие русские войска (дивизия генерал-лейтенанта Повало-Швейковского подошла только 7 апреля), Суворов начинает подготовку войск с обучения австрийцев премудростям штыковой атаки. Получилось очень доходчивое и чёткое руководство: «В строю становиться по локтю. Повороты и деплоирование в обыкновенных случаях делать скорым шагом. Движение производить в колоне повзводно, справа или слева. Шаг в аршин, при захождении — полтора. Фронт выстраивать захождением — повзводно. Готовься к атаке! Тут пальба взводами недолго. По команде «Готовься!» люди задней шеренги отскакивают в сторону, вправо и становятся в две шеренги, а потом вскакивают опять на прежние места. Всем этим заниматься недолго. По сигналу «Марш! Вперёд!» линии двигаются полным шагом и живо. Ружьё в правую руку! Штыки держать вкось без помощи ремня. Как дойдёт до рукопашного, если на кавалерию, то колоть штыком в лошадь и человека; если на пехоту — то штык держать ниже и ближе обеими руками. На 80 саженях картечный выстрел из больших орудий — пехота пробежит вперёд до 15 шагов; то же самое на 60 саженях, когда картечь из малых пушек. Неприятельская картечь летит поверх головы. Когда линия в 60 шагах от неприятеля — офицеры с флангов выбегают вперёд: «Ура, Франц!» Рядовые вперёд — и неприятеля колют… Тут уж только кровь…»