Let $K$ be a closed subgroup of $U(n)$ acting on the $(2n+1)$-dimensional Heisenberg group $H_n$ by automorphisms. One calls $(K,H_n)$ a {\em Gelfand pair} when the integrable $K$-invariant functions on $H_n$ form a commutative algebra under convolution. We prove that this is the case if and only if the coadjoint orbits for $G:=K\ltimes H_n$ which meet the annihilator $\kf^\perp$ of the Lie algebra \kf\ of $K$ do so in single $K$-orbits. Equivalently, the representation of $K$ on the polynomial algebra over $\C^n$ is multiplicity free if and only if the moment map from $\C^n$ to $\kf^*$ is one-to-one on $K$-orbits.
It is also natural to conjecture that the spectrum of the quasi-regular representation of $G$ on $L^2(G/K)$ corresponds precisely to the integral coadjoint orbits that meet $\kf^\perp$. We prove that the representations occurring in the quasi-regular representation are all given by integral coadjoint orbits that meet $\kf^\perp$. Such orbits can, however, also give rise to representations that do not appear in $L^2(G/K)$.