We use the Cluster-EAGLE simulations to explore the velocity bias introduced when using galaxies, rather than dark matter particles, to estimate the velocity dispersion of a galaxy cluster, a property known to be tightly correlated with cluster mass. The simulations consist of 30 clusters spanning a mass range 14.0 ≤ log10(M200 c/M⊙) ≤ 15.4, with their sophisticated subgrid physics modelling and high numerical resolution (subkpc gravitational softening), making them ideal for this purpose. We find that selecting galaxies by their total mass results in a velocity dispersion that is 5-10 per cent higher than the dark matter particles. However, selecting galaxies by their stellar mass results in an almost unbiased (<5 per cent) estimator of the velocity dispersion. This result holds out to z = 1.5 and is relatively insensitive to the choice of cluster aperture, varying by less than 5 per cent between r500 c and r200 m. We show that the velocity bias is a function of the time spent by a galaxy inside the cluster environment. Selecting galaxies by their total mass results in a larger bias because a larger fraction of objects have only recently entered the cluster and these have a velocity bias above unity. Galaxies that entered more than 4 Gyr ago become progressively colder with time, as expected from dynamical friction. We conclude that velocity bias should not be a major issue when estimating cluster masses from kinematic methods.