The viscosity of a suspension of swimming bacteria is investigated analytically and numerically. We propose a simple model that allows for efficient computation for a large number of bacteria. Our calculations show that long-range hydrodynamic interactions, intrinsic to self-locomoting objects in a viscous fluid, result in a dramatic reduction of the effective viscosity. In agreement with experiments on suspensions of Bacillus subtilis, we show that the viscosity reduction is related to the onset of large-scale collective motion due to interactions between the swimmers. The simulations reveal that the viscosity reduction occurs only for relatively low concentrations of swimmers: Further increases of the concentration yield an increase of the viscosity. We derive an explicit asymptotic formula for the effective viscosity in terms of known physical parameters and show that hydrodynamic interactions are manifested as self-induced noise in the absence of any explicit stochasticity in the system.