None of my characters really have much history. I tend to look at a character, get a feel for their key features, and formulate a name that best represents them. A lot of times I'll look up names from other cultures and mix and match, or adapt them to the feel of the world they inhabit.
When I made my first character in EVE, Kaleigh just looked so Celtic, it was hard not to give her a wholesome Irish name. When I later created her sisters, they became an extension of that lineup with Nola and Aideen. Some others have been: Gyra Rho, Valerie Hess, Mei Dan, Solienne Barbier, etc, etc.
Something I'm always cognizant of when designing new character names is how they sound when spoken aloud. They have to roll off the tongue and hopefully conjure in a reader some imagery that relates to the character.