Activating the quest
If you have completed the Dragon Rising main quest, upon heading Whiterun you should come across a couple Redguards wanting to get inside the city. The guards won't be willing to let them in, so the Nomads will have to turn back. Speak to them to learn that their clan (Alik'r) is searching for a Redguard woman who hiding inside the city.
The men won't want to explain why exactly they're looking for their countrywoman, but will offer a big prize for help. If you lack gold, you can consider accepting their offer.
New main objective: Find the Redguard woman
The Redguard woman can be found at The Bannered Mare inn, in the middle of Whiterun. Head inside, turn left and enter the small room where a woman named Saadia is sitting. Tell her that someone is looking for her. She will be very worried and ask you to follow her.
New main objective: Speak with Saadia or Inform the Alik'r of Saadia's location
Follow Saadia onto the upper floor of the inn. As you enter the woman's room, she will take out a knife and start threatening you. Don't attack her - it's more of an act of desperation than real danger. Speak to her to learn that the Alik'rs are looking for her because she opposes the Aldmeri Dominion. If they catch her, they will take her to Hammerfel in shackles and kill her there. The desperate woman will ask you not to tell the Redguards where she's at - it would be catastrophic for her.
You can complete this mission in two ways. If you believe Saadia, skip to Talk to the Alik'r Prisoner. If you prefer to side with the Redguards, skip to Inform the Alik'r of Saadia's location. You won't find any hints pointing to which side is telling the truth - you need to trust your intuition.
New main objective (Saadia): Talk to the Alik'r Prisoner
Head to Dragonsreach and go to the dungeon. Inside one of the cells you will find a Redguard walking across the room. Ask him to tell you the whereabouts of Kematu (Alik'r leader) and he will tell you that he can revel it to you in return for getting him out of the prison. For that, you should find 100 gold in your pocket and pay it to one of the guards as a fine for the man.
After completing the formalities, return to the prisoner. He will give you a location where Kematu is hiding and warn you that heading there is an obvious suicide. All the Mercenaries will attack you as soon as you set foot on their terrain. You need to make preparations for that.
New main objective (Saadia): Kill Kematu
You can find your enemy at the Swindler's Den, west of Whiterun and east of Rorikstead. Head inside and be ready to fight - the cave is swarming with Redguards who will attack you without any hesitation. Fight your way through them or avoid by sneaking and enter the room with a waterfall (look out for the snares!). As you reach the "throne room", Kematu will ask you to put down your weapon. You have already proved your skills.
Approach the Alik'r leader and speak to him. Tell him that Saadia has sent you to kill him and he will laugh at you. The woman has ran away from them multiple times by using suckers like you. In her country, Hammerfell, she is sentenced treason and the Alik'r role is not to kill her, but bring her to fair judgement. If Kematu has convinced you, you can change your decision and join the mercenaries - is such case, skip to Lead Saadia to the Whiterun Stables.
If the man's word didn't make a lasting impression on you, you can tell him that you still intend to kill him. You better move to action right afterwards, as you will have to fight seven Redguards. Try entering the corner of the cave, so that the enemies have to approach you one at a time - it should make the fight much easier. After defeating all of them, head out of the cave and return to Saadia.
New main objective (Saadia): Return to Saadia
After dealing with the Redguards at the Swindler's Den, you can return to Whiterun and tell Saadia that she doesn't have to worry about the mercenaries chasing her anymore. The woman will give you a reward of 500 gold and the plot will end. If you would like to meet with the beautiful woman in the future, you can always find her at The Bannered Mare inn, where she works. She's sure to welcome you warmly.
New main objective (Redguards): Inform the Alik'r of Saadia's location
Alik'rs who are looking for Saadia can be found in Rorikstead, at The Bannered Mare inn. Tell them where the woman is and they will state that they can't seize her here, as it would cause too much commotion in the city. Therefore you will need to help them by leading the woman into the stables - they will wait there and arrest her.
New main objective (Redguards): Lead Saadia to the Whiterun Stables
Return to Whiterun and tell Saadia that the Redguards are on her trail. The woman will start panicking. You should tell her that you have prepared an escape plan for her and that a horse awaits her in the stables, thanks to which she can run from Skyrim. The woman will immediately believe you and follow you. Head to the stables beside the city - the Alik'r will be already waiting there and catch the woman. With Saadia in their hands, they will give you an appropriate reward.
The woman will surely undergo a trial for her treason - you have probably contributed to her death. It's hard to say if justified. The quest ends.