The transient electro-osmotic flow of a generalized Maxwell fluid with fractional derivative in a narrow capillary tube is examined. With the help of an integral transform method, analytical expressions are derived for the electric potential and transient velocity profile by solving the linearized Poisson-Boltzmann equation and the Navier-Stokes equation. It was shown that the distribution and establishment of the velocity consists of two parts, the steady part and the unsteady one. The effects of relaxation time, fractional derivative parameter, and the Debye-Hückel parameter on the generation of flow are shown graphically and analyzed numerically. The velocity overshoot and oscillation are observed and discussed.