Essentially speaking, Newton's 2nd law states that the force applied by a body is equal to the rate of change of its momentum.
Let's say the initial momentum of a body was $mv$, m being its mass and v its velocity, and finally it comes down to $mu$, where u is the reduced (assume) velocity.
The change in momentum is obviously $mv-mu = m(v-u)$.
We assume this change in momentum takes place over a time t. By definition of 'rate', the rate of change of the momentum is then $\frac{mv-mu}{t}$ = $\frac{m(v-u)}{t}$.
Acceleration is defined as the rate of change of velocity, or in other words:
$\frac{v-u}{t} = a$
Plugging this in, we get the rate of change of momentum to be $ma$, which according to Newton's definition is equal to the force. Mathematically:
$F = \frac{m(v-u)}{t} = ma$
To look at it another way, Newton found that:
$F \propto a$
$F \propto m$
thus:
$F \propto ma$
To remove the proportionality sign, we needed a constant of proportionality, which, to define 1N as 1kg times 1m/s$^2$, Newton took to be 1, giving us:
$F = ma$