I skuleåret 1990–1991 arbeidde Solhjell som ufaglært lærar ved Instedalen skule i Naustdal, og i 1995 var han tilsett i Posten i Bergen. I tillegg har han jobba på postkontor i Oslo og ein kort periode i Danmark.
Solhjell var nestleiar i Sosialistisk Ungdom frå 1992 til 1994. Deretter vart han politisk rådgjevar for SVs stortingsgruppe. Han har vore sentralstyremedlem i Sosialistisk Venstreparti sidan 1999. Mellom 2001 og 2005 var han partisekretær i SV. Han vart vald til nestleiar i partiet 25. mars 2007. Valet skjedde under ei kampvotering på partiet sitt landsmøte, der Solhjell fikk 114 stemmer og motkandidaten Ingrid Fiskaa 90 stemmer.
Då Kristin Halvorsen hausten 2011 kunngjorde at ho på partiet sitt landsmøte påfølgande vår ville gå av som partileiar, var Solhjell ein av tre som melde seg som kandidat til vervet. Han trakk seg etter kvart og overlet kampen om leiarvervet til Audun Lysbakken (som vart vald) og Heikki Holmås.
Då Audun Lysbakken våren 2012 trakk seg frå regjeringa, trødde Solhjell igjen inn som statsråd, denne gang som miljøvernminister. Han vart også medlem av Regjeringa sitt underutval, saman med Arbeiderpartiet og Senterpartiet sine leiarar. Solhjell vart dermed SV sin reelle leiarskikkelse i regjeringa og var formelt statsministeren sin stadfortredar.
Hausten 2011 ga Solhjell ut boka Solidaritet på ny, der han skisserte tankar og visjonar for SV si vidare utvikling. Her presenterte han det raudgrøne regjeringssamarbeidet som eit langsiktig strategisk prosjekt som burde vidareførast uavhengig av valresultat.