The regression rate enhancement of hydroxyl-terminated-polybutadiene (HTPB) gaseous oxygen (GOX) hybrid rocket motors was investigated experimentally in a ground testing system. The effects of the addition of nano-sized aluminum (Al) or alloyed aluminum-magnesium (Al-Mg) powder to the fuel composition, mass flux of oxygen, and the oxidizer-fuel ratio on the fuel regression rate are presented. The experiments show that multiple-start and shutdown can be realized using gaseous oxygen/RP-1 pre-mixed torch designed in the present study. The fuel surface remained hot enough during the shutdown interval to reestablish combustion if the time of motor shutdown is less than 2 s. The deduced spatially averaged instantaneous regression rate and spatially and time-averaged regression rate fit well in the trend with time. The former way to calculate the regression rate can more precisely describe the fuel combustion process. As the oxidizer-fuel ratio increased during the test, the hybrid rocket motors didn't work at the optimal oxidizer-fuel ratio, which can induce a loss of specific impulse. The addition of alloyed Al-Mg or nano-sized Al to the HTPB fuel can enhance the regression rate. The effect due to the latter is the most significant.