The fully developed laminar flow of a viscous non-Newtonian fluid in a rough-walled pipe is considered. The fluid rheology is described by the power–law model (covering shear thinning, Newtonian, and shear thickening fluids). The rough surface of the pipe is considered to be fractal, and the surface roughness is measured using surface fractal dimensions. The main focus of this study lies in the theoretical investigation of the influence of the pipe surface roughness on the velocity profile and the Darcy friction factor of an incompressible non-Newtonian fluid. The plotted results demonstrate that shear thinning fluids are the most sensitive to the surface roughness compared with Newtonian and shear thickening fluids. For a particular value of the surface fractal dimension, there exists an intersection point where shear thinning, Newtonian, and shear thickening fluids behave the same way regarding the amplitude of the velocity profile and the friction factor. This approach has a variety of potential applications, for instance fluid dynamics in hydrology, blood flow in the cardiovascular system, and many industrial applications.