Studiowała w Państwowej Wyższej Szkole Muzycznej w Gdańsku w klasie śpiewu Barbary Iglikowskiej (dyplom w 1973). Jest laureatką międzynarodowych konkursów wokalnych w Tuluzie (1971, II nagroda), Paryżu (1972, II nagroda) i s-Hertogenbosch (1973, II nagroda).
Na scenie zadebiutowała w 1972 w Operze Bałtyckiej partią Jadwigi w Strasznym dworze Stanisława Moniuszki. Stworzyła tam wiele kreacji, w tym rolę tytułową w Carmen Georgesa Bizeta, partię Dalili w Samsonie i Dalili Camille'a Saint-Saënsa, Leonory w Faworycie Gaetano Donizettiego oraz bohaterek kilku oper Giuseppe Verdiego. Występowała też w przedstawieniach operetkowych (Student żebrak Karla Millöckera, Noc w Wenecji i Zemsta nietoperza Johanna Straussa).
Stefania Toczyska międzynarodową karierę rozpoczęła w 1977 kreacją Amneris w Aidzie Verdiego w teatrze operowym w Bazylei. Występowała także w Wiener Staatsoper (Rigoletto Verdiego, Carmen u boku Placido Domingo), San Francisco Opera (Gioconda Amilcare Ponchielliego z Luciano Pavarottim i Renatą Scotto, Trubadur Verdiego), Metropolitan Opera House w Nowym Jorku (Chowańszczyzna i Borys Godunow Modesta Musorgskiego, Gioconda, Adriana Lecouvreur Francesco Cilei, Bal maskowy i Aida Verdiego), Covent Garden w Londynie (Trubadur, Aida), Teatro San Carlo w Lizbonie, Bayerische Staatsoper w Monachium (Carmen), Deutsche Oper w Berlinie (Aida), Operze Paryskiej, Teatro Colón w Buenos Aires, na scenach operowych Barcelony, Hamburga, Rzymu, Genewy (Włoszka w Algierze Gioacchino Rossiniego), Zurichu, Pittsburga (Norma Vincenzo Belliniego), Chicago (Anna Bolena Donizettiego), Dallas (Bal maskowy) i Houston (Aida, Norma, Samson i Dalia). Zasłynęła m.in. w rolach Amneris, Carmen, Izabeli (Włoszka w Algierze), Azuceny (Trubadur), Eboli (Don Carlos), Ulryki (Bal maskowy), Rozyny (Cyrulik sewilski Rossiniego), Dulcynei (Don Kichot Julesa Masseneta), Laury (Gioconda) i Maryny (Borys Godunow).