A millisecond pulsar is a neutron star that has been substantially spun up by accretion from a binary companion. A previously unrecognized factor governing the spin evolution of such pulsars is the crucial effect of non-steady or transient accretion. We numerically compute the evolution of accreting neutron stars through a series of outburst and quiescent phases considering the drastic variation of the accretion rate and the standard disk-magnetosphere interaction. We find that, for the same long-term average accretion rate, X-ray transients can spin up pulsars to rates several times higher than can persistent accretors, even when the spin down due to electromagnetic radiation during quiescence is included. We also compute an analytical expression for the equilibrium spin frequency in transients, by taking spin equilibrium to mean that no net angular momentum is transferred to the neutron star in each outburst cycle. We find that the equilibrium spin rate for transients, which depends on the peak accretion rate during outbursts, can be much higher than that for persistent sources. This explains our numerical finding. This finding implies that any meaningful study of neutron star spin and magnetic field distributions requires the inclusion of the transient accretion effect, since most accreting neutron star sources are transients. Our finding also implies the existence of a submillisecond pulsar population, which is not observed. This may point to the need for a competing spin-down mechanism for the fastest-rotating accreting pulsars, such as gravitational radiation.