Gabriel Stephan begann mit dem Tischtennissport beim SV Westgartshausen, einem Ortsteil der Stadt Borgholzhausen im Kreis Gütersloh, Nordrhein-Westfalen. Bereits in jungen Jahren erzielte er mehrere Erfolge. So wurde er zwei Mal Deutscher Meister der Jungen im Doppel, 1999 mit Nico Christ und 2000 mit Fabian Moritz, mit dem er zudem 2002 den Titel bei den Junioren gewann. Im Jahr 2000 wurden Stephan/Moritz in Bratislava Jugend-Europameister durch einen Endspielsieg gegen Constantin Cioti/Dániel Zwickl (ROM/HUN). Bei der Deutschen Meisterschaft 2002 der Erwachsenen holten sie Bronze.