We consider the multi-user MIMO broadcast channel with $M$ single-antenna users and $N$ transmit antennas under the constraint that each antenna emits signals having constant envelope (CE). The motivation for this is that CE signals facilitate the use of power-efficient RF power amplifiers. Analytical and numerical results show that, under certain mild conditions on the channel gains, for a fixed $M$, array gain is achievable even under the stringent per-antenna CE constraint (essentially, for a fixed $M$, at sufficiently large $N$ the total transmitted power can be reduced with increasing $N$ while maintaining a fixed information rate to each user). Simulations for the i.i.d. Rayleigh fading channel show that the total transmit power can be reduced linearly with increasing $N$ (i.e., an O(N) array gain). We also propose a precoding scheme which finds near-optimal CE signals to be transmitted, and has O(MN) complexity. Also, in terms of the total transmit power required to achieve a fixed desired information sum-rate, despite the stringent per-antenna CE constraint, the proposed CE precoding scheme performs close to the sum-capacity achieving scheme for an average-only total transmit power constrained channel.