A method, system and computer program product for performing retiming in the presence of constraints are disclosed. The method comprises receiving an initial design containing one or more targets and one or more constraints and enumerating the one or more constraints and the one or more targets into a retiming gate set. A retiming graph is constructed from the initial design, and a retiming solution is obtained on the retiming graph. The retiming solution is normalized. One or more retiming lags from the retiming graph are propagated to the initial design, and the initial design is verified by using a constraint-satisfying analysis to determine whether the one or more targets may be hit while the one or more constraints are satisfied.