Red blood cells (RBCs) release hemoglobin (Hb)-containing extracellular vesicles (EVs) throughout their lifespan in the circulation, and especially during senescence, by spleen-facilitated vesiculation of their membrane. During ex vivo aging under blood bank conditions, the RBCs lose Hb, both in soluble form and inside EVs that accumulate as a part of storage lesion in the supernatant of the unit. Spontaneous hemolysis and vesiculation are increasingly promoted by the storage duration, but little is known about any physiological linkage between them. In the present study, we measured the levels of total extracellular and EV-enclosed Hb (EV-Hb) in units of whole blood (n = 36) or packed RBCs stored in either CPDA-1 (n = 99) or in CPD-SAGM additive solution (n = 46), in early, middle, and late storage. The spectrophotometry data were subjected to statistical analysis to detect possible correlation(s) between storage hemolysis and EV-Hb, as well as the threshold (if any) that determines the area of this dynamic association. It seems that the percentage of EV-Hb is negatively associated with hemolysis levels from middle storage onward by showing low to moderate correlation profiles in all strategies under investigation. Moreover, 0.17% storage hemolysis was determined as the potential cut-off, above which this inverse correlation is evident in non-leukoreduced CPDA units. Notably, RBC units with hemolysis levels > 0.17% are characterized by higher percentage of nanovesicles (<100 nm) over typical microvesicles (100–400 nm) compared with the lower hemolysis counterparts. Our results suggest an ordered loss of Hb during RBC accelerated aging that might fuel targeted research to elucidate its mechanistic basis.