Parsimony: A newish principle?

Everything should be made as simple as possible, but no simpler – Einstein, paraphrased*
*

KISS- Keep It Simple, Stupid! – unknown*
*

The principle of parsimony seems obvious, reflexive even. Simpler theories should be favored over more complicated ones. And the idea does seem to have been around for a long time, according to Wikipedia  at least since the twelfth century when Maimonides apparently discussed it.

The principle is even embodied in stories of the beginning of experimental science. The heliocentric Copernican theory championed by our hero Galileo could explain the movement of the planets much more simply than the Church's old geocentric theory, with its complicated structure of eccentrics, epicycles, deferents and equants. Parsimony being an obvious advantage of the heliocentric theory, the Church's position was doomed, once everyone got over their religious piety. So the story goes, at least as I always understood it.

I was shocked to read in this online paper that the factor of simplicity was not even raised in Galileo's time!  In the same paper, we're also told that "Copernicus actually introduced epicycles of his own, and even epicycles on top of these".

If not then, when? When did parsimony become a principle of working science?