The complete electroweak O(alpha) corrections are calculated for the charged-current four-fermion production processes e+e- --> nu_tau tau+ mu- anti-nu_mu, u anti-d mu- anti-nu_mu, and u anti-d s anti-c. The calculation is performed using complex gauge-boson masses, supplemented by complex couplings to restore gauge invariance. The evaluation of the occurring one-loop tensor integrals, which include 5- and 6-point functions, requires new techniques. Explicit numerical results are presented for total cross sections in the energy range from the W-pair-production threshold region up to a scattering energy of 2TeV. A comparison with the predictions based on the double-pole approximation (DPA) provided by the generator RacoonWW reveals corrections beyond DPA of < 0.5% in the energy range 170-300GeV, in agreement with previous estimates for the intrinsic DPA uncertainty. The difference to the DPA increases to 1-2% for sqrt{s} = 1-2TeV. At threshold, where the DPA becomes unreliable, the full O(alpha) calculation corrects an improved Born approximation (IBA) by about 1.6%, also consistent with an error estimate of the IBA.