The effect of basil leaf (BLE) and wheat bran (WBE) extracts (potent anti-browning agents), on the phenolic content, antioxidant potential, microbiological quality, and consumer quality of shredded lettuce during storage were studied. Treatment of lettuce with increasing concentrations of BLE proportionally increased the total phenolic content and antioxidant properties. Compared to the control, the treatment enhanced the antiradical properties. This was especially visible during the analysis of the chemical extracts, while this effect was not retained in the potentially bioaccessible fraction. In the lettuce stored for 8 days, the highest reducing potential and ability to quench radicals were observed in samples treated with 1% BLE—33 mg Trolox equivalent/g d.m. and 2.8 mg Trolox equivalent/g d.m., respectively. Compounds exhibiting antiradical properties were easily bioaccessible in vitro. There was no negative effect of the treatments on the consumer quality. Most importantly, after 8 days of storage, lettuce treated with the studied extract, except 10% WBE, had higher microbiological quality. After 8-day storage, the coliforms count was reduced by 84% and 88% in samples treated with 0.5% BLE and 10% WBE, respectively. In conclusion, treatments of shredded lettuce with BLE and WBE maintain or even improve its quality during storage.