Fascinée par l’aviation dès son plus jeune âge, Valérie André profite de la croissance de l’aviation populaire pour prendre ses premiers cours de pilotage dans l’aéroclub de sa ville natale. Contrainte à quitter Strasbourg en 1939, elle entreprend ses études de médecine à Clermont-Ferrand et les achève par la rédaction en 1947 d’une thèse sur « la pathologie du parachutisme », qu’elle étudie en assurant la surveillance médicale d’une préparation militaire parachutiste, effectuant à cette occasion ses premiers sauts.

Sur conseil de son maître de thèse, elle s’engage alors comme médecin capitaine et rejoint l’Indochine en 1949, affectée à l’hôpital de My Tho puis de Saïgon. Son brevet de parachutiste incite alors la hiérarchie à lui proposer d’assurer des missions de largage pour assurer le soutien médical de postes isolés, missions qu’elle accepte malgré leurs difficultés.

Assistant à une démonstration de vol d’hélicoptères, elle mesure aussitôt les avantages que présentent ces engins pour les évacuations sanitaires sur les terrains les plus sommaires. Tenace, elle obtient alors d’être renvoyée en formation en France, où elle obtient la licence de pilote d’hélicoptère à l’école de vol de Pontoise (brevet numéro 33 de l’Aéro-Club de France). De retour en Indochine, elle effectue, entre sa première mission le 16 mars 1952 et son départ de l’Indochine en 1953, 129 vols opérationnels, assurant l’évacuation de 165 blessés.

De 1959 à 1962, elle sert également en Algérie et acquiert, en seulement trois ans de service, les qualifications sur Alouette II, Djinn, Alouette III, Sikorsky H-34 et S-58, ainsi que Vertol H-21, effectuant par la même occasion plus de 350 évacuations sanitaires.