Im Jänner 1997 verkündete Franz Vranitzky seinen Rückzug aus der Politik. Sein Nachfolger wurde der bisherige Finanzminister Viktor Klima. Dieser war vor seiner politischen Karriere bei der Österreichischen Mineralölverwaltung (OMV) tätig gewesen, ab 1992 Minister für öffentliche Wirtschaft und Verkehr im Kabinett Vranitzky, ab 1996 dann Finanzminister.
Im Jahr 1997 wurde nach einer sich über mehrere Jahre erstreckenden Welle von Briefbombenattentaten mit offensichtlich rechtsradikalem Hintergrund Franz Fuchs als Täter gefasst und vor Gericht gestellt. Die Anschlagsserie hatte vier Todesopfer gefordert und 15 zum Teil schwer Verletzte. Im Dezember 1993 wurde auch der Wiener Bürgermeister Helmut Zilk durch eine Briefbombe schwer an der linken Hand verletzt. Im Februar 1995 war eine Sprengfalle im burgenländischen Oberwart explodiert und hatte vier Bewohner einer Roma-Siedlung getötet. Das Gericht verurteilte schließlich den Attentäter zu lebenslanger Haft. Franz Fuchs beging im Februar 2000 Selbstmord.
1997 kam es zur Durchführung mehrerer Volksbegehren, die unterschiedlich erfolgreich waren: Das Anti-Gentechnik-Volksbegehren unterschrieben 1,2 Millionen Menschen, das Frauenvolksbegehren fand 650.000 Unterstützerinnen und Unterstützer.
Ein neues Parteiprogramm
Im Jahr 1998 beschloss die SPÖ ein neues Parteiprogramm, das jenes von 1978 ablösen sollte. In einem langen und intensiven Diskussionsprozess versuchte die Sozialdemokratie, neue Inhalte und eine organisatorische Modernisierung und Öffnung der SPÖ mit den programmatischen Traditionen der Partei rund um die Werte Gleichheit, Freiheit und Solidarität zu verbinden.
Österreichs EU-Präsidentschaft
Im zweiten Halbjahr 1998 hatte Österreich zum ersten Mal die EU-Präsidentschaft inne, was Österreich nutzen konnte, um sich als aktiver, mittlerweile fest verankerter Teil der EU zu präsentieren. Viktor Klima setzte auf EU-Ebene v.a. in der Beschäftigungsfrage wichtige Akzente.
Ende der Großen Koalition
Innerhalb der SPÖ-ÖVP-Koalition kam es immer wieder zu Konflikten. Am Beginn des Wahljahres 1999 standen Kontroversen wie etwa jene um die Rolle der österreichischen Neutralität im Vordergrund. Die SPÖ verteidigte diese vehement, während seitens der ÖVP deutliche Relativierungsversuche unternommen wurden. Die Konflikte in der Koalition sollten sich auch im Ergebnis der Nationalratswahlen im Herbst 1999 niederschlagen. Bei den Wahlen blieb die SPÖ mit rund 33 Prozent der Stimmen zwar stärkste Partei, gleichzeitig gab es starke Zuwächse für die FPÖ, die mit 26,9 Prozent um einige hundert Stimmen mehr als die ÖVP erzielen konnte. Die Grünen erreichten 7,4 Prozent.
Vom 3. Platz zum Bundeskanzler mit FPÖ-Hilfe
Obwohl Wolfgang Schüssel vor den Wahlen unmissverständlich angekündigt hatte, dass die ÖVP in Opposition gehen werde, sofern sie auf den dritten Platz abrutschen würde, stellte sie nach den Wahlen 1999 als drittstärkste Partei bald den Bundeskanzler: Parallel zu den Koalitionsgesprächen mit der SPÖ wurde zwischen Schüssel und Haider schon ein Regierungsbündnis erarbeitet, das in einem Koalitionspakt Anfang 2000 mündete. Entgegen den Präferenzen von Bundespräsident Thomas Klestil wurde die schwarz-blaue Regierung – unter heftigen in- und ausländischen Protesten – im Februar 2000 angelobt, die SPÖ war erstmals seit 30 Jahren wieder in Opposition. Aus den Protesten gegen die Regierungsbeteiligung der FPÖ entwickelten sich die so genannten „Donnerstags-Demonstrationen“ als Ausdruck der kritischen Zivilgesellschaft.
Alfred Gusenbauer neuer SPÖ-Vorsitzender
In der SPÖ trat Viktor Klima nach der blau-schwarzen Koalitionseinigung zurück. Neuer Parteichef und Oppositionsführer der SPÖ im Parlament wurde im Jahr 2000 Alfred Gusenbauer.