Fremstad was born Anna Olivia Rundquist to an unmarried mother in Stockholm. She was adopted there by an American family of Swedish heritage and emigrated with them to the USA when she was 10.
She does not seem to have begun to study music until after the family moved to Minneapolis. She was excellent at the piano, but turned to singing in her teens. She studied in New York and Berlin, and made her professional operatic début in Cologne in 1895 as Azucena in Il Trovatore. She also studied in Italy. Her début at the New York Metropolitan Opera was in 1903 as Siegelinde in Die Walküre. She specialized in Wagnerian roles.
She was very popular, but her limited repertoire, high fees, and prima-donna behavior made her less popular with opera house managers, and she finished at the Met in 1914; her last public performance was in 1920.
Her personal life off-stage was gloomy and self-centered. She married twice, but each soon ended, and she is believed (possibly only on the basis of her close friendships with several prominent lesbians) to have been either lesbian or bisexual.