The intergalactic medium was reionized before redshift z similar to 6, most likely by starlight which escaped from early galaxies. The very first stars formed when hydrogen molecules (H-2) cooled gas inside the smallest galaxies, minihalos (MHs) of mass between 10(5) and 10(8) M-circle dot. Although the very first stars began forming inside these MHs before redshift z similar to 40, their contribution has, to date, been ignored in large-scale simulations of this cosmic reionization. Here we report results from the first reionization simulations to include these first stars and the radiative feedback that limited their formation, in a volume large enough to follow the crucial spatial variations that influenced the process and its observability. We show that, while MH stars stopped far short of fully ionizing the universe, reionization began much earlier with MH sources than without, and was greatly extended, which boosts the intergalactic electron-scattering optical depth and the large-angle polarization fluctuations of the cosmic microwave background significantly. This boost should be readily detectable by Planck, although within current Wilkinson Microwave Anisotropy Probe uncertainties. If reionization ended as late as z(ov) less than or similar to 7, as suggested by other observations, Planck will thereby see the signature of the first stars at high redshift, currently undetectable by other probes.