The difference is a bit subtle. Velocity is speed in a particular direction.
So, for example, a car travelling at 50 miles per hour round a bend is travelling at constant speed. Its direction is changing, however, so its velocity is also changing.
Velocity is always measured from a single point. So an object traveling in a circle has velocity zero relative to the centre of the circle, since the distance from the centre to the object is constant..