This question was actually discussed on this site several times, for example here:
When was the vector notation in physics and other sciences first introduced?
It indeed looks strange to modern people that this simple idea came so late.
Maxwell never uses vectors in his Treatise on electricity and magnetism,
which makes his notation somewhat clumsy.
In fact the idea had a predecessor: quaternions. Yes, quaternions were invented before vectors:-) And Newton did not use vectors in the explicit form.
Instead people thought in very "roundabout", complicated ways about subjects which we routinely treat with vectors nowadays. A striking example is the famous theorem of Apollonius, about "equivalence of excentric and epicycle". Motion on epicycle means that a point moves on a circle around the center (E), while the planet moves on another circle (of smaller radius) around this point. Excentric means that the planet moves on a circle of large radius whose center is different from E, and this center rotates about E (on a circle of small radius). In complex notation, Apollonius theorem says that
To us it seems completely evident that these two things are the same. If you look into Apollonius' proof of this, you see that he really proves commutativity of vector addition in the plane. And Ptolemy praises Apollonius for this.
This frequently happens with simple ideas: after they spread, people start thinking of them as "evident" and wonder how could it happen that their predecessors did not see such simple things. Same thing happened with introduction of matrices to write systems of linear differential equations.