From 1971 to 1978, Vejzović was a member of the Nuremberg Opera, where she appeared in many operas, including principal roles in Orfeo ed Euridice, Carmen, Tannhäuser (as Venus), Intolleranza, Die Soldaten (as Charlotte), Dido and Æneas, Elektra (as Klytemnästra), Il trovatore (as Azucena, directed by Hans Neuenfels in his operatic debut), Boris Godunov (as Marina Mnichek), Wozzeck (as Marie), Aïda (as Amneris), Lulu (as the Countess Geschwitz), and Samson et Dalila.
On 9 October 1978 Vejzović made her Metropolitan Opera debut in Tannhäuser, as Venus, opposite Jess Thomas in the name part, with James Levine conducting.
In 1982, Vejzović debuted at the Teatro alla Scala, as Didon in Les Troyens, conducted by Georges Prêtre and directed by Luca Ronconi.
Another of her great collaborations has been with the director Robert Wilson, in whose productions she sang the title role of Alceste (conducted by Christoph Eschenbach, 1986–87), and in Parsifal (1991 and 1992).
Vejzović has also appeared in Monte-Carlo (Brünnhilde in Die Walküre, 1979), Berlin, Carnegie Hall (the Verdi Requiem, conducted by Lorin Maazel, 1982), Barcelona (Hérodiade, opposite Montserrat Caballé and José Carreras, 1983), Paris (Médée, 1986), Teatro Colón (Kundry, 1986), Vienna (Wozzeck, under Claudio Abbado, 1987; Lohengrin, with Plácido Domingo, 1990), and Houston (Parsifal and Lohengrin, 1992).