Hijo de una familia de comerciantes judíos,[1] de joven conoció el ascenso del antisemitismo, lo que lo convirtió en un activista. En 1928, se unió a la Liga de los Jóvenes Comunistas de Alemania y, dos años más tarde, al Partido Comunista de Alemania, entonces liderado por Ernst Thälmann. Cuando el Partido Nazi tomó el poder en 1933, Goldstein se exilió. Primero trabajó en Luxemburgo como jardinero, para trasladarse más tarde a Francia. En 1935 viajó al Mandato Británico de Palestina.[1]
En 1936, cuando se declaró la guerra civil española y muchos comunistas alemanes acudieron voluntarios a luchar en favor del gobierno de la República Española, Goldstein se unió a ellos en las Brigadas Internacionales. A la finalización del conflicto y con la caída del gobierno, escapó camino de Francia. Como su regreso a Alemania era imposible, fue internado en el Campo de Vernet d'Ariège.[1]
En la Segunda Guerra Mundial, tras la invasión de Francia, consiguió estar tres años sin ser detectado, hasta que en 1942 fue detenido por el Gobierno de Vichy y deportado a Alemania. A su llegada fue internado en el Campo de concentración de Auschwitz donde trabajó acarreando carbón durante 30 meses. De acuerdo al Premio Nobel de la Paz, Elie Wiesel, Goldstein sobrevivió a la marcha de la muerte de Auschwitz a Buchenwald. Cuando este último campo fue evacuado por los nazis el 8 de abril de 1945, los comunistas tomaron el control de campo matando a la guardia que se había quedado. El campo fue liberado oficialmente por tropas estadounidenses el 11 de abril. Goldstein regresó a Alemania, trabajando como periodista, director de radio y escritor.[1]
Fue Presidente (y más tarde con carácter honorario) de los Comités Internacionales de Auschwitz y Secretario de la Fédération Internationale des Résistants.
