The Baltic Sea provides benefits to all of the nine nations along its coastline, with some 85 million people living within the catchment area. Achieving improvements in water quality requires international cooperation. The likelihood of effective cooperation is known to depend on the distribution across countries of the benefits and costs of actions needed to improve water quality. In this paper, we estimate the benefits associated with recreational use of the Baltic Sea in current environmental conditions using a travel cost approach, based on data from a large, standardized survey of households in each of the 9 Baltic Sea states. Both the probability of engaging in recreation (participation) and the number of visits people make are modeled. A large variation in the number of trips and the extent of participation is found, along with large differences in current annual economic benefits from Baltic Sea recreation. The total annual recreation benefits are close to 15 billion EUR. Under a water quality improvement scenario, the proportional increases in benefits range from 7 to 18% of the current annual benefits across countries. Depending on how the costs of actions are distributed, this could imply difficulties in achieving more international cooperation to achieve such improvements.