El Cid
The legendary hero El Cid - real name Rodrigo Díaz - was originally exiled and then went on to conquer the city of Valencia. Overall he was amazing in each aspect of his fighting which was soon displayed with his single combat. He went on to do great things; as mentioned, he took over Valencia but had quite a journey to find himself in that position. He was from a relatively wealthy family but was considered to be one of the working class amongst the people.
The Story
Serving under King Sancho II, El Cid fought in the Battle of Graus, in which he killed a knight in single combat. Remiro Lof Aragon was also killed so they had a good result, which led to his recognition as an impressive soldier. After this he worked for Alfonso VI because Sancho II was assasinated; this wasn't a great event for El Cid, as Alfonso was the brother of Sancho II as well as the person against whom he had been fighting. Rumors soon kicked up that Alfonso had involvement in the assassination; things were soon made things difficult for El Cid and he was removed from his role, which was then given to his rival Ordonez.
Later, in the Battle of Cabra in 1079, El Cid defeated Abd Allah of Granada as well as Ordonez's forces. This infuriated the King, as El Cid hadn't followed the orders given to him. He was subsequently exiled. Instead of fading away as many would do in exile, El Cid offered his fighting services to the Counts of Barcelona. His offer was refused in a decision they would later regret, and El Cid soon found luck with Zaragoza. From there he went on to beat the armies of Leon, Aragon and Castile. Alfonso began to fear a crippling defeat and called El Cid out of exile. El Cid had quite the impressive army of Moors and Christians and marched forward to conquer Valencia.
To achieve his goals he would first have to take care of a few issues along the way, the first of which was Ramon Berenguer II, Count of Barcelona. As he had originally offered his services, El Cid had turned his offer on its head and took power away from the count, keeping him captive for ransom. To keep the peace, El Cid released the count for ransom and also allowed his younger daughter to eventually marry the count's son. From there he traveled around Spain taking cities as he passed, eventually reaching his goal of taking Valencia. He cut up his boundaries and, when he passed away in 1099, his wife took over over power for three years following his death.