André Storelli entre à l'École navale en et en sort enseigne de vaisseau de 2e classe en avec le brevet d'officier de transmission. Enseigne de vaisseau de 1re classe en il embarque sur le sous-marin Diane puis sur le porte-avions Béarn. Officier élève de l’École des officiers transmetteurs en , il embarque sur les contre-torpilleursKersaint en 1936, Vautour en 1937, Gerfaut en 1938 puis Maillé-Brézé en 1939. Il est promu lieutenant de vaisseau en . Il embarque alors sur le croiseur léger Émile-Bertin puis en sur le croiseur léger Montcalm à bord duquel il participe aux opérations de Norvège.
En , il est embarqué sur le contre-torpilleurs Aigle puis est affecté à l'amirauté avant d'embarquer en sur le torpilleur léger Bayonnaise, puis d'être affecté à terre, au Service central de la sécurité navale en .
Il commande en 1944 à Alger le patrouilleur côtier Sabre[1] puis l'aviso colonial Dumont-d'Urville en et est promu capitaine de corvette en décembre. Il est affecté quelque temps à terre à Toulon puis à Paris avant d'embarquer en 1951 sur le croiseur léger Gloire.
Capitaine de frégate en , il embarque en 1952 sur le croiser léger Montcalm puis commande en 1954 l'aviso colonial La Grandière. À Paris en 1955, il est affecté à l’état-major général comme chef de la division transmissions puis comme chef d'état-major de l'escadre légère à Brest en 1957.
Capitaine de vaisseau en , il est auditeur au Centre des hautes études militaires en 1959. Il commande l'école d'application des Enseignes de Vaisseau et le croiseur-école Jeanne-d'Arc de 1961 à 1963[1]. Entre 1962 et 1963, il réussit l'exploit d'un tour du monde sur une seule ligne d'arbre, son bâtiment ayant perdu une de ses hélices à la sortie du canal de Panama.
En , il est désigné au cabinet du ministre des Armées, Pierre Messmer, et est promu contre-amiral en octobre 1964. Adjoint au major général de la marine, il reçoit en le commandement du groupe aéronaval du Pacifique sur le porte-avions Foch lors des campagnes d'essais nucléaires français de 1966 et 1967[1].
