Андре, имевший нрав горячий и склонный к авантюрам, не смог ограничиться однообразной, заполненной трудом жизнью и в возрасте тринадцати лет покинул дом своего дяди, тайком поступив юнгой на торговое судно. Вместе с ним был один из его кузенов по имени Бавастро, ставший во время войн Империи самым известным корсаром Средиземного моря. Андре проплавал юнгой два года, совершив даже путешествие в Америку. Однако усталость и плохое обращение, которое приходилось терпеть на корабле, так ему надоели, что 18 августа 1775 года он нанялся простым пехотинцем в Королевский Итальянский полк, под начало своего дядюшки Марселя, ставшего к тому времени сержант-майором и вскоре произведённого в офицеры. С этим Марселем Массеной я познакомился в 1800 году, в бытность комендантом гарнизона в Антибе. Это был серьёзный и способный человек, которого очень уважал командир его полка, полковник Шове д’Орлон. Желая распространить своё благоволение и на Андре, этот полковник научил его сносно владеть орфографией и французским языком и, несмотря на некоторые его выходки, за несколько лет повысил Андре до чина унтер-офицера, дав ему надежду стать младшим лейтенантом конно-полицейской стражи. Однако, устав ждать повышения, Андре ушёл из армии по истечении своего контракта.
Вернувшись к гражданской жизни и не имея никакого состояния, Андре присоединился к своему кузену Бавастро. Пользуясь близостью границ Франции, Пьемонта, Генуэзского государства и моря, они в крупных масштабах занялись незаконной торговлей, или попросту контрабандой, как плавая в прибрежных районах, так и переходя через горы. В результате Массена досконально узнал все горные тропы в этих местах. Впоследствии, когда ему пришлось командовать здесь войсками, это обстоятельство оказалось ему весьма полезным. Суровая профессия контрабандиста закалила Массену, которому приходилось постоянно угадывать действия таможенников, не раскрывая при этом собственных замыслов. Так, сам того не замечая, Массена научился мыслить по-военному, а также быть бдительным и активным — без этих качеств невозможно стать хорошим офицером. Заработав таким способом некоторый капитал, он женился на француженке мадемуазель Ламарр, дочери хирурга из Антиба, и обосновался в этом городе, где стал понемногу торговать оливковым маслом и сухофруктами. Тут началась революция 1789 года.
Увлекаемый своей склонностью к военной службе, Массена оставил жену и свою лавку и записался в 1-й батальон волонтёров департамента Вар. Его теоретические и практические познания в военном деле сделали его капитаном, а немногим позже — майором. Смелость и активность Массены быстро подняли его до полковника, а затем и до бригадного генерала. Он командовал военным лагерем под названием «Тысяча развилок», где размещалась рота 4-го артиллерийского полка под командой капитана Наполеона Бонапарта. В его подчинении Массене впоследствии пришлось служить в Италии. При осаде Тулона Массене было поручено вести армейскую колонну. Он отличился, овладев фортами Лартиг и Сент-Катрин, за что был произведён в дивизионные генералы. После взятия Тулона он привёл свои войска в Итальянскую армию и снова отличился во всех боях, происходивших на территории между побережьем Средиземного моря и Пьемонтом, в местности, столь хорошо ему знакомой. Массена был умён, отличался замечательной активностью и непоколебимой смелостью, что после многолетних успехов уже сделало его имя знаменитым, как вдруг серьёзная ошибка чуть полностью не разрушила его карьеру.
Начиналась кампания 1796 года. Генерал Бонапарт только что стал главнокомандующим армией, и это поставило под его начало Массену, который когда-то раньше сам был его командиром. Массена в то время командовал авангардом. Разбив в одном из боёв австрийский отряд, он узнал, что в харчевне соседней деревушки вражеские военачальники бросили приготовленным богатый ужин. Вместе с несколькими офицерами Массена собрался овладеть столь замечательной находкой, а свою дивизию оставил в лагере на вершине довольно высокой горы.