We develop Hybrid Monte Carlo (HMC) algorithms for constrained Hamiltonian systems of gauge- Higgs models and introduce a new observable for the constraint effective Higgs potential. We use an extension of the so-called Rattle algorithm to general Hamiltonians for constrained systems, which we adapt to the 4D Abelian-Higgs model and the 5D SU(2) gauge theory on the torus and on the orbifold. The derivative of the potential is measured via the expectation value of the Lagrange multiplier for the constraint condition and allows a much more precise determination of the effective potential than conventional histogram methods. With the new method, we can access the potential over the full domain of the Higgs variable, while the histogram method is restricted to a short region around the expectation value of the Higgs field in unconstrained simulations, and the statistical precision does not deteriorate when the volume is increased. We further verify our results by comparing to the one-loop Higgs potential of the 4D Abelian-Higgs model in unitary gauge and find good agreement. To our knowledge, this is the first time this problem has been addressed for theories with gauge fields. The algorithm can also be used in four dimensions to study finite temperature and density transitions via effective Polyakov loop actions.