Штольпе родился в Штеттине. С 1955 по 1959 годы изучал юриспруденцию в Йенском университете. С 1959 года работал в лютеранской церкви в Берлине-Бранденбурге, одновременно учась в Свободном университете Берлина.
Между 1962 и 1969 годами был руководителем конторы по организации церковных конференций ГДР. После чего становится главой секретариата Федерации лютеранских церквей Германской Демократической Республики. Пробыв на этом посту до 1981 года. В это же время он назначается Всемирным советом церквей в комиссию по международным отношениям.
В 1982-м году Штольпе становится президентом Консистории Восточного региона лютеранской церкви в Берлине-Бранденбурге, и, как член административного совета по организации церковных конференций ГДР, он одновременно был одним из двух заместителей председателя Федерации Лютеранских Церквей. Эти посты он сохраняет вплоть до 1990 и 1989 года соответственно.
В июле 1990 года он присоединяется к социал-демократической партии Германии (СДПГ) и 14 октября того же года избирается в Бранденбургскую государственную ассамблею. Вскоре после этого, 1 ноября 1990 года, он становится премьер-министром земли Бранденбург. Дважды переизбирался, на этой должности он пробыл до конца июня 2002 года.
После выборов в бундестаг 2002 года, Штольпе был приглашён в федеральное правительство Герхарда Шрёдера в качестве министра транспорта, строительства и жилищного хозяйства. В этой роли он запомнился в первую очередь как инициатор развития транспортной системы Восточной Германии.