We present the rest-frame colors and luminosities of ~25,000 mR 24 galaxies in the redshift range 0.2 < z ≤ 1.1 drawn from 0.78 deg2 of the COMBO-17 survey (Classifying Objects by Medium-Band Observations in 17 Filters). We find that the rest-frame color distribution of these galaxies is bimodal at all redshifts out to z ~ 1. This bimodality permits a model-independent definition of red early-type galaxies and blue late-type galaxies at any given redshift. The colors of the blue peak become redder toward the present day, and the number density of blue luminous galaxies has dropped strongly since z ~ 1. Focusing on the red galaxies, we find that they populate a color-magnitude relation. Such red sequences have been identified in galaxy cluster environments, but our data show that such a sequence exists over this redshift range even when averaging over all environments. The mean color of the red galaxy sequence evolves with redshift in a way that is consistent with the aging of an ancient stellar population. The rest-frame B-band luminosity density in red galaxies evolves only mildly with redshift in a Λ-dominated cold dark matter universe. When we account for the change in stellar mass-to-light ratio implied by the redshift evolution in red galaxy colors, the COMBO-17 data indicate an increase in stellar mass on the red sequence by a factor of 2 since z ~ 1. The largest source of uncertainty is large-scale structure, implying that considerably larger surveys are necessary to further refine this result. We explore mechanisms that may drive this evolution in the red galaxy population, finding that both galaxy merging and truncation of star formation in some fraction of the blue star-forming population are required to fully explain the properties of these galaxies.