Background: The study was aimed at screening phytochemicals and evaluating the effects of aqueous and 50% (v/v) methanol stem bark extracts of Newtonia hildebrandtii on male rat reproductive system. Materials and Methods: Thirty male Wistar rats were divided into five groups and were given different treatments of N. hildebrandtii extracts at 200 and 400 mg/kg body weight. After 8 weeks, body and right testis weight, sperm concentration, hormonal levels, and histological structure of the testis were evaluated. Calorimetric method was used for quantitative analysis of phenolic compounds, whereas gas chromatography–mass spectrometry (GC-MS) was used for fingerprinting of chemical compounds. Results: Testosterone, luteinizing hormone, estradiol, and follicle-stimulating hormone levels were significantly increased, whereas prolactin levels were significantly decreased in the treated groups compared to the control. Sperm parameters were significantly increased compared to the control. Treated animals showed significant increases in body weight, seminiferous tubule diameter, and germinal epithelial height with the testes showing all the stages of spermatogenesis. Phytochemical screening of the methanolic extracts revealed the presence of alkaloids, carbohydrates, reducing sugars, steroids, anthraquinones, flavonoids, phenols, and saponins. GC-MS analysis revealed the presence of dimethylsilanediol; (R, R)-2,3-butanediol; hexamethylcyclotrisiloxane; succinimide; 1H-1,2,3-triazole-4-carboxylic acid, 1-(4-amino-1,2,5-oxadiazol-3-yl)-5-ethyl-, ethyl ester; l-(+)-ascorbic acid 2,6-dihexadecanoate; cis-13,16 docasadienoic acid, methyl ester; 9-octadecenoic acid (Z)-, 2-hydroxy-1-(hydroxymethyl) ethyl ester; and 2-chloro-benzoic acid N'-[2-(3-oxo-3,4-dihydro-2H-benzo[1,4]thiazin-2-yl)-acetyl]-hydrazide. Conclusion: N. hildebrandtii appears to possess androgenic and anabolic effects. The aforementioned phytochemicals seem to be responsible for its aphrodisiac effects. This study supports the ethno-aphrodisiac claims that have been made against it.