Excess nutrient loads to coastal waters lead to increased production of algae, which when decaying cause oxygen depletion in bottom sediments, which in turn leads to major changes in marine ecosystems. A cost-minimization model was investigated in which nitrogen and phosphorus were assumed to interact with respect to algae production. It was investigated under what conditions only a single nutrient should be decreased and when it is cost-effective to decrease both nutrients. The model was applied to the Baltic Proper, which is the largest of the seven major basins in the Baltic Sea. Results showed that the stringency of the environmental target, as well as assumptions regarding substitutability between nutrients, are important factors to determine the nutrient on which to focus. Uniform decrease rates for emissions are often used in international agreements, and the results of this model showed that the costs of making such proportional decreases could be substantial.