Travers was born in Southern England, the daughter of a Royal Navy admiral, but grew up in the south of France, where she was a semi-professional tennis player.
At the outbreak of the Second World War, Travers joined the French Red Cross as a nurse, but later became an ambulance driver with the French Expeditionary Force in Finland. With the German invasion of Denmark and Norway, she retreated to Finland. She then escaped by ship to Iceland and returned from there to England where she joined General De Gaulle's Free French Forces. By 1941, she was the chauffeur for a medical officer of the 13th Demi-Brigade of the Foreign Legion, during the Syrian campaign in which Vichy French legionnaires fought Free French legionnaires. She was nicknamed "La Miss" by the legionnaires.
She then travelled to North Africa via Dahomey and the Congo. During that journey, she had a brief affair with Georgian nobleman and Foreign Legion officer Dimitri Amilakhvari. She was then assigned as driver to Colonel Marie-Pierre Koenig and also became his lover.