The availability of stored red blood cells (RBCs) for transfusion remains an important aspect of the treatment of polytrauma, acute anemia or major bleedings. RBCs are prepared by blood banks from whole blood donations and stored in the cold in additive solutions for typically six weeks. These far from physiological storage conditions result in the so-called red cell storage lesion that is of importance both to blood bankers and to clinical practitioners. Here we review the current state of knowledge about the red cell storage lesion from a proteomic perspective. In particular, we describe the current models accounting for RBC aging and response to lethal stresses, review the published proteomic studies carried out to uncover the molecular basis of the RBC storage lesion, and conclude by suggesting a few possible proteomic studies that would provide further knowledge of the molecular alterations carried by RBCs stored in the cold for six weeks.