You can have constraints, if those constraints are holonomic/geometric and can be eliminated by reduction of the configuration space. Eg. if you have spherical pendulum of length $l$ and instead of taking $\mathbb{R}^3$ as the configuration space, you take $S^2$, with spherical coordinates, then you can use the Hamiltonian formalism fine.
If the constraints are such that they appear via multipliers or some other means and they cannot be eliminated by reduction, then the Legendre transform might be ill-defined.
If you are into field theory, then the part of the appendix in Wald's General Relativity that deals with Lagrangian and Hamiltonian formulations might be illuminating. He performs a reduction of the configuration space for electrodynamics, but he shows that so far it is impossible to do so with GR. The Hamiltonian description nontheless works for GR, but this does pose problems for quantization, which Wald once again details.