The velocity dependence of nanoscale friction is studied for the first time over a wide range of velocities between 1 microm s(-1) and 10 mm s(-1) on large scan lengths of 2 and 25 microm. High sliding velocities are achieved by modifying an existing commercial atomic force microscope (AFM) setup with a custom calibrated nanopositioning piezo stage. The friction and adhesive force dependences on velocity are studied on four different sample surfaces, namely dry (unlubricated), hydrophilic Si(100); dry, partially hydrophobic diamond-like carbon (DLC); a partially hydrophobic self-assembled monolayer (SAM) of hexadecanethiol (HDT); and liquid perfluoropolyether lubricant, Z-15. The friction force values are seen to reverse beyond a certain critical velocity for all the sample surfaces studied. A comprehensive friction model is developed to explain the velocity dependence of nanoscale friction, taking into consideration the contributions of adhesion at the tip-sample interface, high impact velocity-related deformation at the contacting asperities and atomic scale stick-slip. A molecular spring model is used for explaining the velocity dependence of friction force for HDT.