"The Celadians", Celadia being a country in the setting. This was not "my" party as such, but the party in the campaign I DM'd for several years, and I'm more or less the one to blame for their name.
At first, they didn't really have any name, though I seem to recall them being known as "Rubin's company" (or "squad" or somesuch) from time to time--Rubin being their NPC superior in the Celadian army. Once they left the army and the country (which had kind of fallen apart, and no it wasn't their fault), some NPCs (i.e. me) started calling them the Celadians. This was somewhat inaccurate, since it's not entirely clear that any of them were actually Celadian (two definitely weren't, and two never specified whether their beloved peasant villages were in Celadia or not). But that's where three of them had come from, from the perspective of the NPCs, so...
The players seemed to like the name, or at least they liked having a name (and the recognition that it implied), so it stuck.
Also it gave me something to call the campaign on Epic Words.