Наградой Наполеону стал чин полного генерала и назначение на пост командующего армией тыла. Его настоящая карьера только начиналась. Однако он не мог полностью воспользоваться плодами этой победы, поскольку из-за своей неотесанности не был вхож в высшее общество и из руководящих кругов был знаком лишь с одним Баррасом.
Этим недостатком Наполеона не замедлила воспользоваться гражданка Жозефина Богарне, 32-летняя креолка, бывшая графиня и вдова генерала Богарне (генерал был казнен в годы террора за плохое исполнение своих воинских обязанностей). Ее лучшей подругой была фаворитка Барраса Тереза Тилльен. Об этих двух женщинах ходили небеспочвенные слухи, что они обе танцевали перед Баррасом в обнаженном виде. Говорили также, что и самой Жозефине пришлось не раз переспать с «директором». Однако это было ей не в новинку — таким делом она занималась со многими высшими чиновниками режима. Широкий круг знакомств этой женщины произвел впечатление даже на. Фуше, главу тайной полиции, который сказал, что «она знает весь Париж». Он даже платил ей иногда за полезную информацию. Когда финансовые дела Жозефины пришли в полное расстройство, инстинкт подсказал ей, что маленький генерал - это та лошадка, на которую следует немедленно сделать ставку, и она постаралась возбудить его сексуальный интерес. Этим достижением, впрочем, ей не пришлось особенно гордиться, поскольку известно, что у Наполеона было по меньшей мере шестнадцать любовниц. Что касается карьеры Наполеона, то Жозефина оказалась ему полезной тем, что ввела его во внутренний мир Директории и убедила Барраса в личной преданности ему Наполеона.
В качестве командующего армией тыла Наполеон отвечал за поддержание законности и порядка в Париже. Он действовал круто, очистив парижскую полицию от тайных роялистов и закрыв клуб якобинского Пантеона. Не забывал он устраивать и свои личные дела. 9 марта 1796 года состоялась свадьба Наполеона и Жозефины Богарне. Он пребывал в плену иллюзий относительно ее немалого состояния (что оказалось блефом) и нуждался в ее контактах с правящей верхушкой. Кроме того, Наполеон и в самом деле влюбился в нее, За неделю до свадьбы его назначили командующим «итальянской армией», что брат Наполеона, Люсьен охарактеризовал как «приданое Барраса» за Жозефиной. Согласно плану Директории Наполеону предстояло перейти Альпы и вторгнуться в Северную Италию. Это вторжение на второстепенном участке фронта должно было сыграть отвлекающую роль и заставить венское правительство раздробить свои силы. Главным же театром военных действий должен был стать запад и юго-запад Германии, через которую французские войска решили попытаться вторгнуться в коренные австрийские владения. Для этой цели были подготовлены самые лучшие корпуса, и возглавлять их были назначены выдающиеся стратеги Моро и Журдан. Под их началом насчитывалось около 160000 солдат; они были прекрасно экипированы и вооружены. Для оснащения этих войск Директория не жалела средств, рассчитывая больше всего именно на них. У Наполеона же было всего 43000 солдат и офицеров, и от него не ожидали особых успехов. План был составлен Карно, бывшим во времена террора «архитектором победы».
Генерал Бонапарт прибыл в свой штаб в Ницце в конце марта 1796 года. О холодном приеме, оказанном ему генералами армии, стали ходить различные легенды, так же, впрочем, как и о способах, которыми он быстро их образумил и заставил беспрекословно выполнять свои приказания. Дело было в том, что эти генералы сначала приняли Наполеона за ловкого интригана, который был обязан своим назначением благосклонному отношению Барраса. Кроме того, план предстоящей кампании они считали неосуществимым. Этими генералами были Ожеро, выбившийся наверх из рядовых пехотинцев и служивший одно время в русской армии, Массена, бывший контрабандист, Лагарп, бывший швейцарский наемник, Серрюрье, ставший прапорщиком в 1754 году, когда ему было 12 лет, и Бертье, произведенный в полковники в 1778 году, во время американской войны. И все они не собирались дать себя запугать «какому-то волосатому коротышке-прощелыге», которому было всего-то 25 лет. И все же, по признанию Ожеро, в Наполеоне было что-то такое, чего они опасались (все они позже стали его маршалами). Отношение к нему генералов мало беспокоило Наполеона, но он пришел в ярость, ознакомившись с подлинным состоянием дел во вверенной ему армии. Те немногие средства, что отпускались Директорией на ее содержание, разворовывались быстро и бесцеремонно 43 тысячи человек жили на квартирах в Ницце и около Ниццы, питаясь неизвестно чем, одеваясь неизвестно во что. Не успел он приехать, как ему сообщили, что одна часть отказалась выполнить приказ о передислокации из-за полного отсутствия обуви у солдат. Развал в снабжении этой заброшенной и забытой армии сопровождался упадком дисциплины. Солдаты воочию видели повальное воровство, от которого они так страдали.
Наполеону предстояло решить ряд сложнейших проблем: он должен был одеть, обуть и привести в порядок весь этот сброд, и сделать это предстояло во время похода. Первое, что он предпринял, - распределил недельный запас хлеба, мяса и водки и отослал в Париж донесение с описанием состояния своего войска. Вместе с тем по своим боевым качествам эти люди были потенциально отличными солдатами; большую часть из них составляли уроженцы Дофине или южных районов. На острове Святой Елены он утверждал, что выпустил следующий приказ по армии: «Солдаты! Вы голодны, босы и раздеты. Я поведу вас на самые богатые в мире равнины, где вы найдете богатые города и провинции. Вас там ждут честь, слава и богатство».
До этого он еще ни разу не водил армию в поход. Ему противостояла грозная сила — войска австрийцев и сардинцев, насчитывавшие 70000 хорошо вооруженных и обученных солдат регулярной армии, уверенных в своей непобедимости. Все проходы через Альпы контролировались ими. 9 апреля 1796 года Бонапарт двинул свои войска вперед, и 12 апреля произошло первое сражение с австрийскими войсками у Монтенотте, в котором австрийцы потеряли 3000 человек убитыми и ранеными. Два дня спустя Бонапарт нанес австрийцам еще одно поражение, на этот раз у Дего, а в промежутке между этими сражениями он наголову разбил пьемонтские войска у Миллезимо, захватив в плен целый корпус. Все эти битвы шли под проливным дождем на высоте более шестисот метров. Остатки пьемонтской армии были разбиты им у Мондови, после чего король Пьемонта запросил перемирия. Это был первый пример «блицкрига» — молниеносной войны, когда противник терпит поражение в первые же дни.
Вслед за этим настал черед австрийцев, которых Бонапарт сокрушил в сражении под Лоди за мост через реку Адду, происшедшем 10 мая 1796 года, причем главнокомандующий лично во главе гренадерского батальона бросился прямо под град пуль и картечи, которыми австрийцы осыпали мост. Именно тогда Бонапарт начал догадываться о том, что его ждет необыкновенная и блестящая судьба. «Я увидел, как все вокруг меня закружилось, словно какая-то неведомая сила подхватила меня и понесла над землей», — так через несколько лет он сказал генералу Горгаду. 15 мая он въехал в Милан, столицу одноименного австрийского герцогства. В июле фельдмаршал Вурмзер предпринял наступление двумя колоннами, имевшее целью снять осаду французов с Мантуи. Наполеон разбил Кваздановича у Локато 3 августа, а двумя днями позже нанес поражение самому Вурмзеру у Кастильоне, взяв в плен 20000 солдат и офицеров с 50 пушками в придачу. Несмотря на полученные подкрепления Вурмзер поспешил укрыться в мантуйской крепости. По иронии судьбы главное французское наступление против Австрии захлебнулось — Журдан потерпел поражение от эрцгерцога Карла, а Моро вынужден был отступить. В ноябре контрнаступление против наполеоновских войск возглавил вновь назначенный австрийский главнокомандующий Альвинци. Но после ожесточенного трехдневного сражения у Аркольского моста он был разбит. В этом сражении Наполеон повторил свой подвиг у Лоди. Трижды французы штурмовали мосты, и трижды их отбрасывали австрийцы, нанося большой урон. И тогда Наполеон со знаменем в руках лично возглавил атаку, завершившуюся взятием моста. Альвинци попытался возобновить активные боевые действия, но опять потерпел поражение у Риволи. Мантуя же капитулировала в феврале.
