We investigate electroosmotic flow of two immiscible viscoelastic fluids in a parallel plate microchannel. Contrary to traditional analysis, the effect of the depletion layer is incorporated near the walls, thereby capturing the complex coupling between rheology and electrokinetics. Toward ensuring realistic prediction, we show the dependence of electroosmotic flow rate on the solution pH and polymer concentration of the complex fluid. In order to assess our theoretical predictions, we have further performed experiments on electroosmosis of an aqueous solution of polyacrylamide (PAAm). Our analysis reveals that neglecting the existence of a depletion layer would result in grossly incorrect predictions of the electroosmotic transport of such fluids. These findings are likely to be of importance in understanding electroosmotically driven transport of complex fluids, including biological fluids, in confined microfluidic environments.