The present investigation considers the thermally developing electroosmotic flow of power-law fluids through a parallel plate microchannel. Both the viscous dissipation and Joule heating effects are taken into account and a step change in wall temperature is considered to represent physically conceivable thermal entrance conditions. Expressions for the dimensionless temperature and Nusselt number in the form of infinite series are presented. In general, the resultant eigenvalue problem is solved numerically; nevertheless, an analytical solution is presented for the regions close to the entrance. A parametric study reveals that increasing amounts of the Peclet number result in higher wall heat fluxes, whereas the opposite is true for the flow behavior index. Furthermore, based on the value of the dimensionless Joule heating parameter, the Nusselt number may be either an increasing or a decreasing function of the axial coordinate or even both of them in the presence of a singularity point. The viscous heating effects are also found to be negligible.