They didn't invent coordinates as such -- a coordinate system was used by Ptolemy in his Geography more than 1000 years earlier.
The major novelty in the work of Descartes and his contemporaries was not the use of coordinates to describe a single point, but the idea that a single algebraic relation between the two coordinates can describe an entire family of points -- i.e., a curve.
This idea must have been "in the air" at the time, and the final ingredient of it that had just arrived seems to have been improvements in algebraic notation, with letters standing for known and unknown quantities alike, which made manipulations of equations, formulas and recipes for calculation easy enough to be useful for analyzing geometric situations. Only with good notation in place did it become natural to think of an algebraic relation as a "thing" among other similar things that could be an "object of thought" rather than just some particular canned sequence of actions.
The improved notation had been in development for at least a couple of centuries, with algebraists gradually freeing themselves from the classical/medieval tradition of describing everything in prose, figuring out the proper laws for manipulating different powers of the unknown, and inventing convenient notation to go with it. Descartes himself was among the first to use recognizably modern algebraic notation (and is credited with the idea of letters from the beginning of the alphabet (a, b, c, ...) for constants and letters from the end of the alphabet (x, y, z, ...) for unknowns).