Geological carbon sequestration mitigates climate change by capturing and storing carbon dioxide (CO2) emissions in deep geologic formations. Dissolution trapping is one mechanism by which CO2 can be trapped in a deep formation. However, heterogeneity can significantly affect the dissolution efficiency. This work addresses the injection of CO2 in perfectly stratified saline formations under uncertainty. Monte Carlo two-phase flow compositional simulations involving the dissolution of CO2 into brine and evaporation of water into the CO2-rich phase are presented. We systematically analyzed the interplay between heterogeneity (sigma(2)(Y) ) and gravity factor (G), which is shown to control the migration of the CO2 plume as well as the temporal evolution of dissolution efficiency. Results show that when G is important, vertical segregation controls the overall behavior of CO2 , diminishing the influence of small-scale heterogeneity on dissolution. However, when G is relatively small compared to sigma(2)(Y), CO2 migrates preferentially through high permeability layers and dissolution efficiency increases with sigma(2)(Y) due to the stretching of the CO2 plume that enhances mixing. As a result, in this situation, the upscaling of permeability leads to an underestimation of the dissolution efficiency. A review of field sites shows that dissolution is heterogeneity-controlled in most real systems. Knowing that most numerical models cannot afford to represent heterogeneity at an adequate scale, results indicate that dissolution efficiency can be typically underestimated by a factor close to 1.5.