After her studies in Trondheim, Oslo and København, her international breakthrough came as Octavian in Der Rosenkavalier (The Knight of the Rose) at the Opéra Bastille in Paris in 1993. She had the same success with this role in London. Her interpretation of Silla in Hans Pfitzner's opera Palestrina at Covent Garden rocketed her to the Metropolitan Opera in New York City.
As a soloist, Randi Stene has performed at BBC Proms with Esa-Pekka Salonen and at the Salzburg Festival with Philippe Herreweghe. She is also a frequent guest soloist with the symphony orchestras in the Nordic capitals. Given her base in Copenhagen and her key role within Danish opera, she was an obvious choice as a soloist at the inauguration of the new opera house in Copenhagen in the new production of Verdi's Aida. Her recordings includes songs by Hugo Alfvén, John Dowland, Edvard Grieg, Wilhelm Peterson-Berger and Jean Sibelius.