I'm creating my character for a new campaign, and as it's only my third campaign I'm struggling a bit. 

I have been wanting to make a Tiefling for a long time, initially I wanted her to be a warlock but I found that the personality I was giving her was alot like my first character and my current - quiet, self-destructive, good, etc. 
So now I'm thinking Lawful Evil Paladin to spice it up a little. 

I wrote out part of the backstory as her ancestors noble bloodline being cursed by Beshaba. 

Is this possible? Can a Tiefling be a Paladin? 
How can I make sense of her being that class when she's a Tiefling? 
Would it just be easier to be a Chaotic Evil/Any evil Rogue or something similar? 

Thanks