Nach dem Besuch der Volksschule absolvierte Steppuhn in den Jahren 1977 bis 1980 eine Lehre zum Stahlbetonbauer und leistete anschließend von 1981 bis 1982 Wehrdienst.
Danach war er bis 1987 in seinem erlernten Beruf bei einem Bauunternehmen in Minden tätig und ließ sich dann zum Organisationssekretär beim DGB ausbilden.
Im Jahr 1989 wurde er Jugendsekretär beim DGB-Landesbezirk Niedersachsen/Bremen und 1990 Organisationssekretär beim DGB-Kreis Minden-Lübbecke. Noch 1990 wechselte er als Fachreferent zum Bundesvorstand der IG Bau-Steine-Erden in Berlin. Von 1991 bis 2001 war Steppuhn Landesvorsitzender der IG BAU in Sachsen-Anhalt.
Im Jahr 1980 trat Steppuhn in die SPD ein. Von 1999 bis 2017 war er Landesvorsitzender der SPD-Arbeitsgemeinschaft für Arbeit (AfA) in Sachsen-Anhalt und war von 2000 bis 2011 Vorsitzender des AfA-Bundesausschusses.
Andreas Steppuhn scheiterte bei der Bundestagswahl 2009 am 27. September 2009 im Bundestagswahlkreis Harz (Wahlkreis 69) beim Kampf um das Direktmandat mit 20,3 % der Erststimmen.[3] Da er nur über Platz 6 auf der Landesliste der SPD abgesichert war, schied er aus dem Bundestag aus.
Andreas Steppuhn übernahm am 14. März 2016 nach der Landtagswahl in Sachsen-Anhalt 2016 das Amt als SPD-Fraktionsvorsitzender von der bisherigen Landes- und Fraktionschefin Katrin Budde.[4] Im April 2016 gab er das Amt an Katja Pähle ab. Er war stellvertretender Fraktionsvorsitzender und Sprecher für Arbeitsmarktpolitik, Rentenpolitik, Integration und Gegen Rechtsextremismus.