The child of a Malagasy mother and a French father, a financial director at Air France, Verissimo spent her childhood in France, the United States, and Nigeria. She began performing in pornography at 18 and a half years old, performing in films by John B. Root, the adult film director who she worked with exclusively through her entire 16-month adult film career. During this time, she called herself "Ally Mac Tyana", which was a play on the name Ally McBeal. She appeared in such adult videos as Ally, French Beauty and Xperiment, and on Root's website Explicite.com.
In 2002, she had her first non-erotic film roles, as an extra in So Long Mister Monroe and an appearance on an episode of the French police dramaBrigade des mineurs. In 2004, she was cast as Lola in the film Banlieue 13, a role specially created for her by producer Luc Besson.
In May 2006, in the ELLE magazine for the Special Cannes Edition she was recognized as one of the new upcoming actresses.