Né à Nice, descendant d'une longue lignée de petit négociant, sa mère lui donnait des soins tout particulier car sa santé était fragile. Une légende rapporte qu'un soir André s'empare d'une branche de laurier en fleur. Un médecin survenu à ce moment blâma sa mère disant que la fleur de laurier est vénéneuse. Le petit refusa énergiquement de lâcher son butin et s'endormit avec. Le lendemain, miracle, il s'éveilla plein de vigueur. Puis comme sa mère il porta toute sa vie les débris de cette fleur dans un médaillon.

Orphelin vers 8 ans, il n'eut pas d'instruction et se fit mousse à onze ans. La mer n'étant pas sa voie, cet homme aux cheveux noirs et drus, de petite taille s'engage au Royal Italien en 1775. Ayant trouvé des maîtres pour l'instruire, il rattrape le temps perdu.

Congédié en août 1789 avec le grade d'adjudant, il est élu lieutenant-colonel par les volontaires du Var en février 1792 et sert à l'armée d'Italie jusqu'en 1798. Son expérience militaire lui permet de faire une rapide carrière : général de brigade en août 1793, général de division en décembre suivant après s'être distingué au siège de Toulon.

Placé sous les ordres de Bonaparte de 10 ans son cadet, il en conçoit de la rancœur mais s'efforce de prouver ses qualités par une suite d'exploits, forçant le passage du pont de Lodi (10 mai 1796), entrant le premier à Verone (3 juin), écrasant les Autrichiens à Lonato (3 août).