The sustained biomass of pelagic Sargassum in nutrient-poor waters of the Sargasso Sea has long been a paradox in biological oceanography. To better understand the mechanisms supporting growth of Sargassum over its broad geographic range in the western North Atlantic, we measured growth rate, gross productivity, and C:N:P ratios of both Sargassum natans and Sargassum fluitans from a variety of neritic (Caribbean Sea, Straits of Florida, Gulf Stream) and oceanic (Sargasso Sea) locations. In neritic areas, the abundance of associated fishes was quantified with a purse seine net designed to minimize fish avoidance of sampling gear. Abundant fish species were also collected for measurements of ammonium and soluble reactive phosphorus excretion rates. Low growth rates and productivity of both S. natans and S. fluitans were associated with high C:N and C:P ratios in oceanic populations in the Sargasso Sea, confirming strong nutrient-limitation in this oligotrophic gyre. In comparison, both species from the neritic areas had higher productivity and growth rates and lower C:N and C:P ratios, indicating relatively nutrient-enriched growth. Sargassum windrows in neritic locations had high abundances of associated fishes (mean of 128 fishes/kg wet weight Sargassum), especially juvenile filefish Stephanolepsis hispidus (Monacanthidae) and jacks (Carangidae). High excretion rates of ammonium and soluble reactive phosphorus were associated with these mutualistic fishes, which can provide nutrients needed to sustain growth and biomass of Sargassum. These findings suggest that new production of Sargassum occurs in neritic waters of the western North Atlantic Ocean and Gulf of Mexico, where mutualistic relationships with fishes, especially juvenile filefishes and carangids, contribute to nutrient supply and growth.