Background: Recent reviews suggest that the warming and acidification of ocean surface waters predicated by most accepted climate projections will lead to mass mortality and declining calcification rates of reef-building corals. This study investigates the use of modeling techniques to quantitatively examine rates of coral cover change due to these effects. Methodology/Principal Findings: Broad-scale probabilities of change in shallow-water scleractinian coral cover in the Hawaiian Archipelago for years 2000-2099 A.D. were calculated assuming a single middle-of-the-road greenhouse gas emissions scenario. These projections were based on ensemble calculations of a growth and mortality model that used sea surface temperature (SST), atmospheric carbon dioxide (CO2), observed coral growth (calcification) rates, and observed mortality linked to mass coral bleaching episodes as inputs. SST and CO2 predictions were derived from the World Climate Research Programme (WCRP) multi-model dataset, statistically downscaled with historical data. Conclusions/Significance: The model calculations illustrate a practical approach to systematic evaluation of climate change effects on corals, and also show the effect of uncertainties in current climate predictions and in coral adaptation capabilities on estimated changes in coral cover. Despite these large uncertainties, this analysis quantitatively illustrates that a large decline in coral cover is highly likely in the 21st Century, but that there are significant spatial and temporal variances in outcomes, even under a single climate change scenario.