Flow of typical non-Newtonian fluids such as cement grouts can experience different regimes as the Reynolds number (Re) changes, understanding of which is important for design and operation of rock grouting in various rock engineering applications. Here, flow regimes of representative non-Newtonian fluids, i.e., Bingham and Herschel–Bulkley (H–B) fluids, are numerically investigated with experimental validations. Three tensile rock fracture surfaces originated from a fine-grained sandstone, a medium-grained sandstone and a medium-grained granite samples are used to create rough-walled fracture models with variable aperture structures. Flow of groundwater, Bingham and H–B fluids through these fractures is numerically simulated respectively, by solving the full mass and momentum conservation equations with the Re ranging from 0.01 to 1000. The regimes for these fluids flowing through the fractures are characterized. Laboratory flow tests are conducted in a cylindrical granite fracture sample to verify the characterized flow regimes. The results reveal important differences of flow regimes between Newtonian and non-Newtonian fluids. Specifically, the transmissivity for water flow is constant when Re is relatively small until the Re reaches certain critical values; the transmissivity for Bingham and H–B fluids flow increases with increasing Re until asymptotically reaches certain peak values, followed by a descending stage when Re is relatively large. The critical (water) and peak (Bingham and H–B fluids) values are affected by surface roughness, that is, a rougher surface results in smaller critical and peak values as well as greater discrepancies compared to the analytical solutions based on the smoothed parallel plates model. These results show that a peak or optimum transmissivity is achievable in a specific range of Re (Re = 10–100 for the fractures studied). This new finding can potentially help optimize the injection pressure or flow rate in rock grouting practices.