The kinesin family proteins are often studied as prototypical molecular motors; a deeper understanding of them can illuminate regulation of intracellular transport. It is typically assumed that they function identically. Here we find that this assumption of homogeneous function appears incorrect: variation among motors' velocities in vivo and in vitro is larger than the stochastic variation expected for an ensemble of "identical" motors. When moving on microtubules, slow and fast motors are persistently slow, and fast, respectively. We develop theory that provides quantitative criteria to determine whether the observed single-molecule variation is too large to be generated from an ensemble of identical molecules. To analyze such heterogeneity, we group traces into homogeneous sub-ensembles. Motility studies varying the temperature, pH and glycerol concentration suggest at least 2 distinct functional states that are independently affected by external conditions. We end by investigating the functional ramifications of such heterogeneity through Monte-Carlo multi-motor simulations.