The blood storage lesion involves morphological and biochemical changes of red blood cells (RBCs) that occur during storage. These include conversion of the biconcave disc morphology to a spherical one, decreased mean corpuscular hemoglobin concentration, varied mean corpuscular volume, reduced integrity of the erythrocyte membrane with formation of microparticles, and increased cell-free hemoglobin. We studied the extent that older stored red blood cells scavenge nitric oxide (NO) faster than fresher stored red blood cells. Using electron paramagnetic resonance spectroscopy and stopped-flow absorption spectroscopy to measure the rate of NO uptake and reaction with hemoglobin in red cells, we found that older stored red blood cells scavenge NO about 1.8 times faster than fresher ones. Based on these experimental data, we simulated NO scavenging by fresher or older stored red blood cells with a biconcave or spherical geometry, respectively, in order to explore the mechanism of NO scavenging related to changes that occur during blood storage. We found that red blood cells with a spherical geometry scavenges NO about 2 times slower than ones with a biconcave geometry, and a smaller RBC hemoglobin concentration or volume increases NO scavenging by red blood cells. Our simulations demonstrate that even the most extreme possible changes in mean corpuscular hemoglobin concentration and mean corpuscular volume that favor increased NO scavenging are insufficient to account for what is observed experimentally. Therefore, RBC membrane permeability must increase during storage and we find that the permeability is likely to increase between 5 and 70 fold. Simulations using a two-dimensional blood vessel show that even a 5-fold increase in membrane permeability to NO can reduce NO bioavailability at the smooth muscle. Background: Transfusion of older stored blood may be harmful. Results: Older stored red blood cells scavenge nitric oxide more than fresher cells. Conclusion: As stored red blood cells age, structural and biochemical changes occur that lead to faster scavenging. Significance: Increased nitric oxide scavenging by red blood cells as a function of storage age contributes to deleterious effects upon transfusion. © 2014 The Authors.