Objective. This study was a multicenter, randomized, double-blind, and controlled trial with two parallel arms: the GJBNH group and the placebo group. This trial recruited 100 women aging 18 to 35 years with primary dysmenorrhea caused by blood stagnation. The investigational drugs, GJBNH or placebo, were administered for two menstrual periods (8 weeks) to the participants three times per day. The participants were followed up for two menstrual cycles after the administration. Results. The results were analyzed by the intention-to-treat (ITT) dataset and the per-protocol (PP) dataset. In the ITT dataset, the change of the average menstrual pain VAS score in the GJBNH group was statistically significantly lower than that in the control group. Significant difference was not observed in the SF-MPQ score change between the GJBNH group and the placebo group. No significant difference was observed in the PP analyses. In the follow-up phase, the VAS scores of the average menstrual pain and the maximum menstrual pain continually decreased in the placebo group, but they increased in the GJBNH group. Conclusion. GJBNH treatment for eight weeks improved the pain of the dysmenorrhea caused by blood stagnation, but it should be successively administered for more than two menstrual cycles. Trial Registration. This trial is registered with Current Controlled Trials no. ISRCTN30426947.