So, this question got me thinking. If, say, the Pokemon using Fake Out was holding a Quick Claw, and the Quick Claw worked that turn and the Fake Out user was faster, would it hit through a Protect?
If the Pokémon using Fake Out is faster than the one using Protect, then Fake out will strike first. Also, since both moves have high priority, gaining extra priority due to items or abilities, the Pokémon using Fake Out will strike first.
So yeah, it's basically who is faster. Or...
Since the Pokémon with the quick claw has added priority (Fake Out and Protect both have +3 priority), it will go first
Source: The neat little link here and Experience.
Hope I helped! =]