We report a measurement of the proton-air cross section for particle production at the center-of-mass energy per nucleon of 57 TeV. This is derived from the distribution of the depths of shower maxima observed with the Pierre Auger Observatory: systematic uncertainties are studied in detail. Analyzing the tail of the distribution of the shower maxima, a proton-air cross section of {[}505 +/- 22(stat)(-36)(+28)(syst)] mb is found.