He was German Champion winning at Bad Oeynhausen 1942. He took 8th in the (unofficial) European Championship at Munich 1942 (Alexander Alekhine won). In 1943, he took 6th in Salzburg (Paul Keres and Alekhine won). In 1943, he took 5th in Vienna (10th GER-ch; Josef Lokvenc won).
He represented Germany at fifth board in 3rd unofficial Olympiad at Munich 1936, and won two bronze medals (team and individual). Rellstab played for West Germany thrice in Chess Olympiads.
He won individual gold medal at Helsinki 1952 and team bronze medal at Dubrovnik 1950.
Awarded the IM title in 1950.