Protons and helium nuclei are the most abundant components of the cosmic radiation. Precise measurements of their fluxes are needed to understand the acceleration and subsequent propagation of cosmic rays in the Galaxy. We report precision measurements of the proton and helium spectra in the rigidity range 1 GV-1.2 TV performed by the satellite-borne experiment PAMELA. We find that the spectral shapes of these two species are different and cannot be well described by a single power law. These data challenge the current paradigm of cosmic-ray acceleration in supernova remnants followed by diffusive propagation in the Galaxy. More complex processes of acceleration and propagation of cosmic rays are required to explain the spectral structures observed in our data.