EOF of non-Newtonian power-law fluids in a cylindrical microchannel is analyzed theoretically. Specially, exact solutions of electroosmotic velocity corresponding to two special fluid behavior indices (n = 0.5 and 1.0) are found, while approximate solutions are derived for arbitrary values of fluid behavior index. It is found that because of the approximation for the first-order modified Bessel function of the first kind, the approximate solutions introduce largest errors for predicting electroosmotic velocity when the thickness of electric double layer is comparable to channel radius, but can accurately predict the electroosmotic velocity when the thickness of electric double layer is much smaller or larger than the channel radius. Importantly, the analysis reveals that the Helmholtz-Smoluchowski velocity of power-law fluids in cylindrical microchannels becomes dependent on geometric dimensions (radius of channel), standing in stark contrast to the Helmholtz-Smoluchowski velocity over planar surfaces or in parallel-plate microchannels. Such interesting and counterintuitive effects can be attributed to the nonlinear coupling among the electrostatics, channel geometry, and non-Newtonian hydrodynamics. Furthermore, a method for enhancement of EOFs of power-law fluids is proposed under a combined DC and AC electric field.