In Canada (Attorney General) v. Bedford, the Supreme Court struck down Canada’s prostitution laws on the basis that they violated prostitutes’ right to security of the person and were inconsistent with the principles of fundamental justice under section 7 of the Canadian Charter of Rights and Freedoms. This paper examines the implications of Bedford for the constitutional norms against arbitrary, overbroad and grossly disproportionate laws. It is argued that Bedford significantly advances the law on these principles of fundamental justice by clarifying the tests governing their application, by elucidating the ir inter-relationships, by distinguishing the constitutional analysis applicable under these principles from the section 1 proportionality analysis, and, most importantly, by demonstrating that the principles against arbitrariness, overbreadth and gross disproportionality remain alive and capable of meaningfully constraining legislative choice. The analysis also touches on the future regulation of prostitution in Canada, and suggests that the law as laid out in Bedford leaves Parliament with some room to choose between regulatory options. Specifically, it is argued that criminalizing prostitution may remain constitutionally permissible after Bedford.