[1] En 1974, Randy Stoklos empezó a jugar vóleibol de playa en Muscle Beach, Venice, California con Joe Gold.
Ganó su primer torneo de clase "A" en 1976 en Sorrento Beach.
Luego, su primera victoria como profesional fue en 1981 en el Abierto de Manhattan junto a Jim Menges, torneo el cual ganó junto con Jim Menges, Adam Johnson y Sinjin Smith.
En 1982, Randy Stoklos ganó el Campeonato Mundial de Voleibol de Playa durante su primer año dedicado por completo al tour, junto con su compañero Sinjin Smith, con quien ganó el mismo torneo en 1988 y el U.S.
En 1991, fue nombrado MVP en el tour de Italia, Brasil y Australia.