Praworęczny, wysoki Amerykanin (195 cm) preferował styl gry serwis–wolej i z powodzeniem startował w grze podwójnej. Jako deblista wygrał 13 turniejów z cyklu ATP World Tour oraz osiągnął 5 finałów, a w maju 2000 roku zajmował 18. miejsce w rankingu światowym. W 2001 roku, mając za partnera Scotta Humphriesa, doszedł do półfinału Wimbledonu; ponadto cztery razy był wielkoszlemowym ćwierćfinalistą w deblu, po raz ostatni w Australian Open z 2006 roku, gdy na jego drodze (oraz Ashleya Fishera) stanęli Mariusz Fyrstenberg i Marcin Matkowski. Gimelstob często zmieniał partnerów deblowych – turnieje wygrywał wspólnie z dziesięcioma różnymi tenisistami, z którymi też notował zwycięstwa nad takimi parami, jak Bob Bryan–Mike Bryan czy Mark Woodforde–Todd Woodbridge.
Największe sukcesy w karierze Gimelstoba to dwa tytuły wielkoszlemowe w grze mieszanej. W 1998 roku Amerykanin, wspólnie z Venus Williams, triumfował w Australian Open, w finale pokonując Helenę i Cyrila Suków 6:2, 6:1. Rodzinny akcent miał też drugi triumf pary Gimelstob–Williams, bowiem w finale French Open w 1998 roku przyszło im zmierzyć się z siostrą Venus, Sereną, której partnerował Luis Lobo.