Dissolution trapping of CO2 in brine can reduce the risk of leakage of supercritical CO2 during long-term Geological Carbon Sequestration (GCS). The dissolution of overlying gaseous CO2 into brine increases the density of brine in its upper portion, which causes gravity-driven convection (GDC) and thus significantly increases the rate of CO2 dissolution. To date, most studies on GDC-driven dissolution are based on homogeneous media and only few studies exist on the effect of heterogeneity on GDC-driven dissolution. Here, we study the effect of heterogeneity on GDC-driven dissolution rate by using numerical simulations with randomly obtained permeability fields. Dissolution rates calculated by these simulations are related to properties of the permeability field by using least-squares regression. We obtained two empirical formulas for predicting the asymptotic GDC-driven dissolution rate. In the first formula the dissolution rate is almost linearly proportional to the dimensionless equivalent vertical permeability. In the second one the dissolution rate is linearly proportional to a dimensionless vertical finger-tip velocity. Both formulas show a non-linear relation between dissolution and anisotropy with higher anisotropy giving lower dissolution rates.