How can we achieve the conflicting goals of reduced transmission power and increased capacity in a wireless network, without attempting to follow the instantaneous state of a fading channel? In this paper, we address this problem by jointly considering power control and multiuser detection (MUD) with outage-probability constraints in a Rayleigh fast-fading environment. The resulting power-control algorithms (PCAs) utilize the statistics of the channel and operate on a much slower timescale than traditional schemes. We propose an optimal iterative solution that is conceptually simple and finds the minimum sum power of all users while meeting their outage targets. Using a derived bound on outage probability, we introduce a mapping from outage to average signal-to-interference ratio (SIR) constraints. This allows us to propose a suboptimal iterative scheme that is a variation of an existing solution to a joint power control and MUD problem involving SIR constraints. We further use a recent result that transforms complex SIR expressions into a compact and decoupled form, to develop a noniterative and computationally inexpensive PCA for large systems of users. Simulation results are presented showing the closeness of the optimal and mapped schemes, speed of convergence, and performance comparisons.