Widespread coastal eutrophication is known to increase the prevalence of harmful algal blooms (HABs). Increased HABs have also been linked to climate change, with ocean warming predicted to lead to increased prevalence and earlier timing of HABs. Testing the predictions of warming to HABs is difficult due to the lack of long-term observations across spatial scales. Here, we use a 45 year (1970–2015) record of the occurrence and duration of HABs along Chinese coast to show that the HAB frequency has increased at a rate of 40 ± 4% decade–1, with earlier timing by 5.50 ± 1.78 days decade–1. The increasing frequency of blooms varied with latitude and is significantly correlated with warming at an average rate of 0.17 ± 0.03 °C decade–1, with the positive relationship being strongest in more eutrophic provinces. HAB frequency increased with elevated dissolved inorganic nutrient concentration, but this increase was amplified further with warming. Warming and eutrophication showed additive roles in triggering HABs. Swift action to mitigate eutrophication is essential to avoid a sharp increase in the HABs in coastal waters with further warming.