Strøm-Erichsen wuchs in Fridalen in Bergen auf und besuchte bis 1968 das Gymnasium Langhaugen. Ihr Vater arbeitete als Jurist für die Kommune Bergen. An der Ingenieurshochschule Bergen ingeniørhøgskole studierte sie von 1970 bis 1974 elektronische Datenverarbeitung. Anschließend arbeitete sie bis 1984 für die EDV-Abteilung der Universität Bergen. Im Jahr 1977 trat Strøm-Erichsen in die Arbeiderpartiet ein. Von 1980 bis 1981 studierte sie an der South Dakota School of Mines and Technology. Nach 1984 arbeitete sie für unterschiedliche Unternehmen.[1][2]
Bei der Kommunalwahl im Jahr 1991 zog sie in den Stadtrat von Bergen ein. Von 1995 bis 1998 war sie Kommunalråd, als welche sie für den Schulbereich zuständig war. Im Jahr 1997 wurde sie zur Vorsitzenden der Arbeiderpartiet im damaligen FylkeHordaland gewählt. Sie blieb bis 1999 im Amt. Ab 1998 fungierte Strøm-Erichsen als stellvertretende Bürgermeisterin der Stadt. Im Anschluss an die Kommunalwahl 1999 wurde sie zur Bürgermeisterin von Bergen gewählt.[1] Sie war die erste Frau, die den Bürgermeisterposten in Bergen bekleidete. Als Bergen im Jahr 2000 auf ein System mit einem sogenannten Byråd umstieg, wurde Strøm-Erichsen die erste Vorsitzende des Byråds.[2][3] Als solche fungierte sie bis zur nächsten Kommunalwahl im Jahr 2003. Danach war sie zwei weitere Jahre Mitglied im Bergener Stadtrat. Sie war in den Jahren 1999 bis 2001 Präsidentin der Organization of World Heritage Cities[1]
Strøm-Erichsen zog bei der Parlamentswahl 2005 erstmals in das norwegische Nationalparlament Storting ein. Dort vertrat sie den Wahlkreis Hordaland.[1] Am 17. Oktober 2005 wurde sie in der neu gebildeten Regierung Stoltenberg II zur Verteidigungsministerin ernannt.[4] Aufgrund ihrer Regierungsmitgliedschaft musste sie in der gesamten Legislaturperiode 2005–2009 ihr Mandat ruhen lassen. Sie wurde im Storting deshalb von ihrem Parteikollegen Dag Ole Teigen vertreten.[1] Bei der Wahl 2009 zog sie ein zweites Mal in das Parlament ein. Etwas nach der Stortingswahl wechselte sie am 20. Oktober 2009 von ihrem Posten als Verteidigungsministerin zum Posten der Gesundheits- und Pflegeministerin. Es war zu diesem Zeitpunkt zu einem größeren Umbruch in der Regierung von Jens Stoltenberg gekommen. Zum 21. September 2012 wechselte Strøm-Erichsen im Rahmen einer erneuten Kabinettsumbildung zurück ins Amt der Verteidigungsministerin. Ihr Amt übte sie bis zum Abtritt der Regierung am 16. Oktober 2013 aus.[4] Auch während ihrer zweiten Legislaturperiode, die bis Herbst 2013 andauerte, musste Strøm-Erichsena vertreten werden. Ihre feste Vertreterin im Parlament war die Arbeiderpartiet-Politikerin Tove Linnea Brandvik.[1]
Zur Parlamentswahl 2013 trat Strøm-Erichsen nicht mehr erneut an. Dass sie nicht erneut kandidieren wolle, hatte sie im Mai 2012 verkündet.[5] Nach ihrer Zeit als Ministerin wurde sie 2014 Beraterin bei der PR-Agentur Rud Pedersen.[6]
