C and F clefs were used for plainsong pretty much from the start of staff notation. On the 4-line staff, the C clef could be on either of the top two lines, and the F clef was equivalent to the C clef one line above the staff.
The earliest known printed music dates from about 1465. G clefs for the top part were certainly in use by 1508 when Petrucci printed this (see page 14 of the PDF):
https://imslp.org/wiki/Special:ImagefromIndex/307180/torat - the Superius part from http://imslp.org/wiki/Motetti_a_cinque_(Petrucci,_Ottaviano).
The basic motivation for selecting clefs was to avoid leger lines. The modern F and G clefs are equivalent to a C clef on the leger line above or below the staff, so they are perhaps not such a big innovation as they might at first appear. In early music notation, the G clef was sometimes used on the bottom line for violin parts, and the F clef on the top line for low bass voice parts - those are equivalent to extending the range of C clef positions to two leger lines either side of the stave.
The F clef was sometimes used on the middle line as an alternative to the C clef on the top line.
A final random thought - I wonder why all known clefs indicate the pitch on a line, and never a space. That fact is enough to "explain" the existence of both F an G clefs - but why?
