Instructions
Travel to the act and difficulty where you hired your current mercenary. Rogue scouts are hired in Act I, Iron Wolves are hired in Act III and barbarians are hired in Act V. All of them can be hired in any difficulty. Desert mercenaries with Prayer, Defiance or Blessed Aim auras are available in Act II both Normal and Hell difficulty, while desert mercenaries with Thorns, Holy Freeze or Might auras are available in Act II in Nightmare difficulty only.
Open the mercenary inventory by pressing the "O" key and remove all of your current mercenary's equipment. If you don't, you will lose it once you hire the new mercenary.
Click on the mercenary recruiter and select "Hire" to open a list of available mercenaries. In Act I, the mercenary recruiter is Kashya, in Act II Greiz, in Act III Asheara and in Act V Qual-Kehk.
Click on the mercenary whose name you like the best and select "Yes" when prompted.