Flavonoids are potent scavengers of reactive oxygen species (ROS) that effectively prevent erythrocyte oxidation. Their antioxidant activities are governed by their structural characteristics and their ability to interact with and penetrate lipid bilayers. In order to gain a better understanding of the relationship between cholesterol contents and the antioxidant effectiveness of flavonoids against oxidative damage induced by ROS in cells, here we analyzed the integrity and structural stability of cholesterol-modified (enriched or depleted) and control erythrocytes exposed to tert-butyl hydroperoxide in the presence of quercetin or rutin. In control and cholesterol-enriched erythrocytes, quercetin provided greater protection against lipid peroxidation, ROS formation, and it preserved better cellular integrity than rutin. Both antioxidants suppressed the alterations in membrane fluidity and lipid losses with similar efficiency, reducing hemoglobin oxidation by 30% and GSH losses by 60% in the above-mentioned erythrocytes. Cholesterol depletion reduced the efficiency of the antioxidant power of both flavonoids against oxidative damage induced in the erythrocyte membrane, while a stronger degree of protection of GSH and hemoglobin contents was observed, mainly in the presence of rutin. These findings suggest a preferential incorporation of the antioxidants into the membranes from erythrocytes with normal and high cholesterol contents, whereas they would mainly be located in the cytoplasm of cholesterol-depleted erythrocytes.