We consider an optimal stopping problem where a constraint is placed on the distribution of the stopping time. Reformulating the problem in terms of so-called measure-valued martingales enables us to transform the distributional constraint into an initial condition and view the problem as a stochastic control problem; we establish the corresponding dynamic programming principle. The method offers a systematic approach for solving the problem for general constraints and under weak assumptions on the cost function. In addition, we provide certain continuity results for the value of the problem viewed as a function of its distributional constraint.