Postharvest romaine lettuce is susceptible to water loss, loss of greenness, and tissue softening because of its high water content and fluctuations in storage temperature and Relative Humidity (RH). However, the relationships among quality changes, odor fingerprints, and microbial communities have not been comprehensively evaluated. To compare storage quality under different temperature and RH conditions and characterize microbial communities in representative storage states and to develop an environment-based quality prediction method, a 3 × 3 factorial storage experiment was conducted at 4, 13, and 25°C and 65%, 80%, and 90% RH. Weight loss, maximum puncture force, color, and pH were measured over 0–12 d. Odor fingerprints were assessed with a PEN3 electronic nose (Airsense Analytics GmbH, Schwerin, Germany), and metagenomic sequencing was performed on three representative storage states. A Comprehensive Quality Index (CQI) was constructed and evaluated by grouped cross-validation. Greater water loss, loss of greenness, and decline in puncture force were observed at 25°C, whereas water loss was primarily reduced by higher RH. At 12 d, weight losses of 65.35% and 25.45% and maximum puncture forces of 302.03 and 467.87 gf were recorded in the 25°C/65% RH and 4°C/90% RH groups, respectively. Odor fingerprints of the 25°C/65% RH and 4°C/90% RH groups were clearly differentiated at 9–12 d, and a significant difference in genus-level community structure was detected among the representative states (Analysis of Similarities: R=0.88, P=0.005). The highest mean CQI over 3–12 d was recorded in the 4°C/90% RH group (76.33). In leave-one-group-out cross-validation, an Out-of-Fold (OOF) coefficient of determination (R2) of 0.93 and a Root Mean Square Error (RMSE) of 4.10 were obtained with the ridge regression model. Quality deterioration was slowed by low temperature combined with higher RH. Within the experimental range, CQI and its prediction model can be used to compare storage quality and predict quality trends, providing a quantitative basis for cold-chain temperature and humidity management.