The prevailing view in international legal practice is that a state does not waive its immunity from execution by merely consenting to arbitration. Yet, in the context of arbitration between states and private parties, execution immunities have emerged as a very significant obstacle to the effective implementation of arbitral awards. When immunity from execution allows states to escape obligations they have freely undertaken, and when it withholds from claimants the fruits of a favourable award, the benefits of arbitration become illusory. This article contends that the prevailing view is no longer compelling because, in the context of arbitration, deference to state immunity is misplaced and imposes an unjustified limit on the rule of law. It is suggested that an agreement to arbitrate should ultimately have the presumptive effect of waiving immunity from execution. The proposed waiver may be viewed as following from the obligation that the sovereign voluntarily undertakes when submitting to arbitration, and tracks the normative evolution of the relation between the doctrine of sovereign immunity and arbitration law.