Newtonian mechanics is based on two principles:
Space and time are absolute. The time coordinates given to observations in all inertial frames are related by a constant time shift. In particular, all observers in all inertial frames agree on the time interval between any two events.
The physical laws take the same form in all inertial frames. This is the principle of relativity.
Together these two principles imply the Galilean transformation can be used to transform positions, velocities and accelerations between inertial frames. The Galilean transformation implies the acceleration in one inertial frame is the same as the acceleration in any other. Because position and velocity are not the same in all inertial frames, the principle of relativity implies that no physical law can be a function of position or velocity (though a physical law may be a function of distance between two points, since distance does not change between inertial frames).
The discovery of the Lorentz force law for a charged particle moving in a combination of electric and magnetic fields –- does depend explicitly on the velocity. This implies that either this is not a fundamental force of nature, or that Newtonian mechanics is flawed.
In fact the second of these turned out to be the case. The postulates of Newtonian mechanics above were replaced by the postulates of special relativity:
The speed of light is the same in all inertial frames
The physical laws take the same form in all inertial frames.
The first of these is a consequence of Maxwells' Laws. The second is the principle of relativity, which is retained. Time is no longer absolute. Different observers may disagree over the time interval between events and even about the order in which events occur. Physical laws may depend explicitly on velocity (and the Lorentz force law becomes a fundamental law of nature).
The constancy of the speed of light was implied by experiment well before the special theory of relativity was formulated, and was long a source of controversy. Scientists hypothesised a fluid which filled all space and called it the ether. They thought the speed of light could be measured relative to the ether and might have speedcalculated from physical constants, but relative to an observer might have some other speed. In fact they found the speed of light to have the same speed relative to all observers. This is now just one of many experimental pieces of evidence in favour of special relativity.