Scars of the Past
I forget the name of the desert, but it is on the main continent that the world is built on, Khorvaire, and it falls between the Talenta Plains and Valenar. The Talenta Plains is a large region of lands mostly populated by the Talenta Halflings, a nomadic group of people who live a simple, but interesting life. The power structure of House Ghalanda (The house of hospitality) still exist today on the Plains, even though the house has many enclaves in cities throughout the world. Valenar is a nation of elves. The Valenar are the descendants of the Aerenal elves who settled on Khorvaire long ago.
Anyway, instead of being settled in one area, your tribe would probably have been more nomadic, roaming from place to place trying to survive and keep their desert heritage intact despite the world around them changing constantly. There would always be work for someone in the desert to help those that need a guide across the harsh plain. It could be that the men you killed were actually Valenar elves. While Valenar is by no means an evil nation, even elves have their bad apples. While you and one of your people were guiding three of the Valenar across the desert, they started drinking and bragging about how inferior your camels were to their Valenar steeds (Valenar are famed for their horse-breeding). They got drunk one night, leading to the incident. Instead of killing all three elves, however, one of them survived and escaped.
When you returned to your people and your companion told them what you had done, you were shunned and outcast. Knowing that you could not flee to Valenar, you fled into the desert for a time, where you almost died of thirst. A lone traveler found you and gave you water and listened to your story. He seemed to know much of the desert, but was strange in his mannerisms and dress. The desert heat did not seem to affect him like it did most outsiders, but his skin was too pale for him to have spent much time in the desert. He gave you the name Arek Mahmuud, and you spent several weeks with him, learning to use a sword and the ways of tracking and nature. When you asked how you could repay him, he merely smiled and asked you to do a small errand for him. He gave you something wrapped in heavy parchment and asked you to deliver it to a dwarf named Teldorthan Stoneshaper in the town of Fallcrest in Northeast Breland. He says it is a long journey, but you will learn much about the land and yourself on the way. He gives you enough gold to make the trip, and during the night, while you are sleeping, he leaves. Strangely though, he leaves no tracks indicating what direction he went when he left…