Stoch was born in Heidenheim an der Brenz in 1969. After graduating from high school in 1989, he studied law from 1990 to 1995 at the universities in Tübingen and Heidelberg. He was a trainee lawyer at the district court of Ellwangen and attended the administrative college in Speyer. Stoch passed his second state examination in 1997 and worked as an independent lawyer with a focus on civil and commercial law in Heidenheim from 1998.^[3]

Stoch was district chairman of the Young Socialists (Jusos) from 1987 to 1991, and joined the SPD itself in 1990. He became leader of the Heidenheim SPD association in 1999.

On 1 April 2009, Stoch became a member of the Landtag of Baden-Württemberg. He succeeded Wolfgang Staiger, who had resigned, and was given a second mandate for the SPD in the Heidenheim constituency. In the 2011 state election, Stoch was the SPD's candidate for the Heidenheim constituency. He won 29.8% of votes, placing second to the CDU's Bernd Hitzler. He was elected to state parliament via a proportional seat.^[4] From 2011 to 2013, he was his party's parliamentary managing director and spokesman for legal and media policy.

Stoch was appointed as Minister for Culture, Youth and Sport in 2013 to replace fellow SPD member Gabriele Warminski-Leitheußer, who resigned in early January.^[2]

Stoch was re-elected to the Landtag in the 2016 state election. However, he won just 19.4% of votes, third behind the Greens' Martin Grath (26.1%) and incumbent CDU deputy Bernd Hitzler (25.1%).^[5] The SPD's performance statewide substantially worsened, falling to fourth place, and they did not return to government after the election. Stoch thus resigned from cabinet along with the other SPD ministers. After the election, Stoch became leader of the SPD parliamentary group.

After the defection of four members from the Alternative for Germany (AfD) parliamentary group during July to October 2016, the SPD became the third largest group. Since the two largest groups, the Greens and CDU, were in government, the SPD became the largest opposition party. Stoch thus became leader of the opposition, succeeding Jörg Meuthen.

On 24 November 2018, Stoch was elected leader of the state branch of the SPD at a party conference, succeeding Leni Breymaier. He won 50.6% (159 votes) against Lars Castellucci, who won 48.1% (151 votes).^[1]

On 1 February 2020, Stoch was nominated as the SPD's lead candidate for the 2021 state election.^[6] Following the elections, he led his party's delegation in the negotiations with Minister-President Winfried Kretschmann's Green Party on a potential coalition government.^[7]

In the negotiations to form a so-called traffic light coalition of the SPD, the Green Party and the FDP following the 2021 federal elections, Stoch led his party's delegation in the working group on education policy; his co-chairs from the other parties are Felix Banaszak and Jens Brandenburg.^[8]