Let K be a closed subgroup of U(n) acting on time (2n + 1)-dimensional Heisenberg group H-n by automorphisms. One calls (K, H-n) a 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 x H-n which meet the annihilator l(perpendicular to) of the Lie algebra l 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 l(+) 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 l(perpendicular to). We prove that the representations occurring in the quasi-regular representation are all given by integral coadjoint orbits that meet l(perpendicular to). Such orbits can, however, also give rise to representations that do not appear in L-2(G/K).