At age 17 Paul Gelhaar stood in goal for VfB Königsberg and in May 1923 helped them reach the semi-finals of the German championship, drawing attention to his talent. With his new club Hertha BSC Berlin, he four times reached the final of the German Cup. In 1928 and 1929 they lost the final, but the team won in 1930, against Holstein Kiel, and in 1931, against TSV 1860 München. In 1928 Gehlhaar was nominated as a reserve goalkeeper behind Nürnberg keeper Heiner Stuhlfauth for the Olympic football tournament in Amsterdam, but did not play. Gehlhaar earned two international caps. He was later the owner of a gas station in Berlin-Zehlendorf.