We consider the problem of optimally stopping a continuous-time process with a stopping time satisfying a given expectation cost constraint. We show, by introducing a new state variable, that one can transform the problem into an unconstrained control problem and hence obtain a dynamic programming principle. We characterize the value function in terms of the dynamic programming equation, which turns out to be an elliptic, fully non-linear partial differential equation of second order. We prove a classical verification theorem and illustrate its applicability with several examples.