NOTE: Quest not available as of version 2.0, but the sword is still obtainable from the cheat/debug menu
Valar Doehaeris can be started in the castle of Braavos. If you speak to Menzo Mhor Kastos, you will get the quest. For the quest you have to take over Volantis. Just the city of Volantis is enough for this quest to complete, you don't have to fully defeat the kingdom of Volantis.
A word of warning: When the Khirza Khalisar comes and takes Volantis, you may be planning to take it from them. If you do so, the Targaryens, Dragonstone and The Westerlands declare war on you. (If I remember correctly - it's basically anyone fighting for the crown in Westeros)