Tropical coral reefs are among the most biologically diverse and economically important ecosystems on earth. Nevertheless, we found dramatic changes in coral communities on the reef slopes of Curaçao and Bonaire since 1973. Cover and abundance declined for virtually all coral species. The data show a shift from communities dominated by framework building species (e.g., Orbicella spp.) to communities consisting of small opportunistic, phenotypically plastic, species, including few remaining structural colonies. Madracis mirabilis, Porites astreoides, Diploria strigosa, and Agaricia lamarcki are at present modest winners in the coral assemblage, although overall cover declined also for these species. Increased frequency and intensity of events inducing coral mortality and ongoing reduction in suitable hard substratum, provided by the remnants of large colony building species, could reduce the chance of these species to remain winners in the longer run. The observed loss in coral cover and the shift from larger structural to smaller opportunistic species reduced reef carbonate production by 67% and therewith, in combination with a trend toward smaller coral colonies, reef complexity. Alarmingly, reefs at upper-mesophotic depths (30–40 m) did not escape the general degradation of the coral community. The negative effects are larger around densely populated areas where local stressors are adding to degradation caused, for instance, by region wide mass bleaching. Without proper conservation and management this already dramatic degradation will continue and turn more and more coral species into losers.