I'm trying to flush out my character a little bit; all I really know right now is that her father was a human soldier, while her mother an Elven cleric. Are there locations where paladins come from in the DnD world specifically? Or can they be entirely original? I know that some world are original; this is my first campaign aside from the starter set which I just finished, which that character won't be going anywhere.

From my understanding most of the modules released for 5e take place in the Forgotten Realms. Paladins can come from anywhere.

If they're sponsored by a church, maybe a big city like Amn. If they're an Oath of the Ancients maybe they come from one of the elf homelands. You can pretty much choose what ever you like for a background from an RP standpoint. 

Maybe your Paladin was a criminal, living on the streets before some thief god chose them as their champion and imbued them with their favor. 

Maybe they were a pirate and learned the error of their ways.

Interesting ... I think that just gave me some ideas right there. Definitely for the beginning of the story ... I was thinking something along the lines of her village or town having been invaded when she was a child, and then her mission is to lead forces against the warriors from the outside. Will have to look up places and cultures from the forgotten realms, though, in order to do this right, I think.

To me Adventurers are weird people.  It's much more sensible to stay home and do anything else other then delve dungeons and fight dragons.  If you just sold all the magic items, you'd love modestly for the rest of your life.  No, Adventuresr are crazy.

I like to look for inspiration in Joseph Cambell.  As an Adventurer your already completed a minor Hero's Journey... Now you can't return home yet, and must heed the Call to Adventure.

So pretty much any Background can work.

Backgrounds I'm a fan of are the Knight varient of Noble. This gives you 3 loyal NPC retainers, so you need but in from your GM.  It's nice to be able to hands wave sending messages and setting up camp... If your in heavy armor, self you put it on!

Urchin/Criminal/Pirate you were one a villian but you'd had a experience that changed you and your on the path of righteous now instead.

I don't think I have any restrictions, I'll check, though.

Acolyte also works very well given the religious synergy, as does a folk hero if you're playing a low-key paladin.

Never thought of that one.

I like acolyte, basically I'm a missionary spreading the word of Bahamut to the masses.  Pairs well with a persuasion proficiency to try and get converts.  

My paladin used to be a medic in the army till a costly mistake. She went into the forest and found some standing stones and sat down to contemplate the mistake when she was approached by a mysterious lady. 

I made mine a unique homebrew, close to criminal, prisoner. He's a blue dragonborn who has lived in prison since he was 15. He was imprisoned by a neighboring clan. Around his 30th, he was released from by a Paladin order who worshipped Thor. Upon his release, he swore the Oath to be a Holy Warrior of Thor's. Been doing it for 4 years now. (Meta: Jumped into a game where the others were level 4, so I aged it so it seemed right.)

Personally I was a really big fan of the "Knight of the Order" background in the SCAG. Lot of open ended versatility in which skill you actually get, and what band of knights you hailed from. Using that I made a kenku paladin of Lurue. 

I think I'll have to read up a bit more in order to know who those folks are. Hopefully I'll find some Paladin content within the pages of R. A. Salvatore? I just started reading his stuff.

There is something incredibly-dark and unique about a Paladin (I'm thinking Vengeance but there are other possibilities starting at Level 3) with the Haunted One Background:

"I don’t run from evil. Evil runs from me. I live for the thrill of the hunt.", "I have a dark calling that puts me above the law. (Chaotic)", "I would sacrifice my life and my soul to protect the innocent."

Another concept I enjoyed was a Paladin of Mystra (Oath of the Ancients) with the Mulmaster Aristocrat Background. His lover, a Priest of Mystra (and a man, they are a homosexual couple), was imprisoned by The Cloaks for criminal acts of worship.

I find noble works just, has the right amount synergy and conflict for real interesting holy warrior.

I have plans on a devotion/divine Sorcadin sailor. His focus is a loa talisman he calls Jambuki. He will possibly dip hexblade and make a pact with the "loa spirits". He is highly superstitious, enjoys a friendly wager, and loves telling lavish stories embellishing the truth for flavor and effect.

My other Paladin idea is an Oath of the Ancients Folk Hero that got his start arming the peasants of his small town to overthrow a tyrant.

For ideas, I go to http://1-dot-encounter-planner.appspot.com/pc-personality-generator.html and click the button a few times until I get something interesting. Then I will modify it to taste and go from there. For some GMs it can be helpful for a player to just make stuff up to provide them with possible hooks and ideas from your background. Try to give him/her something to work with. Remember that customizing backgrounds is part of the rules. If you find something in your background doesn't quite fit, feel free to pull from a different one or just make something up that does. If you have Xanathar's Guide, go ahead and roll on the "This Is Your Life" tables(pg 61) to give yourself inspiration.

Thanks for that! I think I'll not get to roll until the 30th (when I see my friends again, (hopefully we'll be able to actually play, though)). In my group, our DM is very much a storyteller, and he ensures that we are just as much a part of the character planning as he is. 

I know this doesn't apply to your half elf, but I really got into my newest characters build. Dragonborn Oath of Ancients.  who grew up in the valley in a small community that lived and worked under the protection of a legendary gold dragon.  I witnessed a group of murder hobos (from some stupid evil campaign) slay the dragon and felt and saw the dragons presence leave the surrounding area and that sorrow was enough that the community sent there 4 most promising young Dragonborn out on path dedicated to protecting the Light of this world and following a oath older then any silly empire that will crumble and fall.

I really like the Dragonborn / Oath of the ancients pairing. I honestly never made that connection. If I may; I feel that a green Dragon (forest) being the presence lost is a great "story" for a Dragonborn (any heritage) to be asked by the ancients to replace. It sort of puts the choice of the ancients champion in the hands of the unseen ancients, vice... the community of presumably non ancient folk. but I can see your story rockin it too.

I've been mulling over the notion of a black dragonborn with the gladiator background who becomes a vengeance paladin.

  I'm playing a paladin in my friends campaign. Usually I DM but she wanted to give it a whirl. Figured it be easier for her if at least one of her characters was the traditional knight in shining armor type. My character's name John. I went with the Urchin background so no parents, no last name. John begged, borrowed, and stole what he needed to survive well into his teens. He probably would have become a rogue if not for one fateful day when he was caught with his hand in the pocket of the wrong noble.

  Beaten and bloodied John was left outside the city walls to die. He was found there by an aging Green knight who took him to his patron, an Arch Fey Princess. John was healed and indoctrinated into her order of knights. (Oath of the Ancients.) John's a stunning example of knight hood worn too tightly by a boy who was once destined for a darker path. So if she turns out be a really good DM I can ditch tradition at get edgy. It's all about options.