De fin Janvier 1959 à Mars 1962, Valérie André sert en Algérie en tant que commandant adjoint du service médical à la base aérienne 142 de Boufarik, puis à partir de 1961 elle est nommée médecin-chef de la base et commandant de l’hélicoptère de service de sauvetage stationné sur la base aérienne 146 de Reghaïa, à Oran.
Devenue pilote d’hélicoptère SA-318 Alouette II, puis Sikorsky H-34, durant ses missions, elle effectue plus de 350 évacuations sanitaires.