The Wilkinson Microwave Anisotropy Probe (WMAP) has mapped the full sky in Stokes I, Q, and U parameters at frequencies 23, 33, 41, 61, and 94 GHz. We detect correlations between the temperature and polarization maps significant at more than 10 standard deviations. The correlations are present in all WMAP frequency bands with similar amplitude from 23 to 94 GHz, and are consistent with a superposition of a CMB signal with a weak foreground. The fitted CMB component is robust against different data combinations and fitting techniques. On small angular scales theta < 5 deg, the WMAP data show the temperature-polarization correlation expected from adiabatic perturbations in the temperature power spectrum. The data for l > 20 agree well with the signal predicted solely from the temperature power spectra, with no additional free parameters. We detect excess power on large angular scales (theta > 10 deg) compared to predictions based on the temperature power spectra alone. The excess power is well described by reionization at redshift 11 < z_r < 30 at 95% confidence, depending on the ionization history. A model-independent fit to reionization optical depth yields results consistent with the best-fit LambdaCDM model, with best fit value tau = 0.17 +- 0.04 at 68% confidence, including systematic and foreground uncertainties. This value is larger than expected given the detection of a Gunn-Peterson trough in the absorption spectra of distant quasars, and implies that the universe has a complex ionization history: WMAP has detected the signal from an early epoch of reionization.