Aside from the Fimbriani mentioned by Tom, I don't think we know of any legion names prior to 44BC. Cicero, writing to Atticus in that year, mentions the
legione alaudarum commanded by M Antonius. Later, in the Philippics (I.8 ), he refers to a
legio Martia in Octavian's army. The first of these is, of course, the famous Alaudae - later given the number V - raised by Caesar from the noble volunteers of Transalpine Gaul (Suetonius, Caesar 24). The number of the 'legion of Mars' is unknown.
Perhaps it's significant that legion names are first found in a time of civil war - with legions on the opposing sides often holding the same number, names might have been necessary to distinguish the different armies. Certainly names occur with increasing frequency after 44 on inscriptions. The civil wars also gave birth to the Augustan 'standing army', of course, so perhaps various unofficial legion nicknames that had been around for a while were given a more official sanction.
If we assume that Caesar's 10th legion were named
Equestris due to their providing a mounted escort during the meeting with Ariovistus in 58, then this might be the earliest recorded legion name. But Caesar himself never mentions it, and neither does anyone else! (see Keppie,
The Making of the Roman Army, p137). The name isn't recorded until after Philippi, I believe. Another name attested for the 10th is
Veneria, and this might actually be older - recall the
Martia mentioned by Cicero, a similar 'divine' legion name. I wondered
some time ago whether the 'original' name for the 10th might have been X
Veneria Equestris, after the goddess Venus Equestris, a Roman form of Astarte... but I digress!
- Nathan