The incidence and intensity of hypoxic waters in coastal aquatic ecosystems has been expanding in recent decades coincident with eutrophication of the coastal zone. Worldwide, there is strong interest in reducing the size and duration of hypoxia in coastal waters, because hypoxia causes negative effects for many organisms and ecosystem processes. Although strategies to reduce hypoxia by decreasing nutrient loading are predicated on the assumption that this action would reverse eutrophication, recent analyses of historical data from European and North American coastal systems suggest little evidence for simple linear response trajectories. We review published parallel time-series data on hypoxia and loading rates for inorganic nutrients and labile organic matter to analyze trajectories of oxygen (O2) response to nutrient loading. We also assess existing knowledge of physical and ecological factors regulating O2 in coastal marine waters to facilitate analysis of hypoxia responses to reductions in nutrient (and/or organic matter) inputs. Of the 24 systems identified where concurrent time series of loading and O2 were available, half displayed relatively clear and direct recoveries following remediation. We explored in detail 5 well-studied systems that have exhibited complex, non-linear responses to variations in loading, including apparent "regime shifts". A summary of these analyses suggests that O2 conditions improved rapidly and linearly in systems where remediation focused on organic inputs from sewage treatment plants, which were the primary drivers of hypoxia. In larger more open systems where diffuse nutrient loads are more important in fueling O2 depletion and where climatic influences are pronounced, responses to remediation tended to follow non-linear trends that may include hysteresis and time-lags. Improved understanding of hypoxia remediation requires that future studies use comparative approaches and consider multiple regulating factors. These analyses should consider: (1) the dominant temporal scales of the hypoxia, (2) the relative contributions of inorganic and organic nutrients, (3) the influence of shifts in climatic and oceanographic processes, and (4) the roles of feedback interactions whereby O2-sensitive biogeochemistry, trophic interactions, and habitat conditions influence the nutrient and algal dynamics that regulate O2 levels.