Atmospheric deposition of mineral dust supplies much of the essential nutrient iron to the ocean. Presumably only the readily soluble fraction is available for biological uptake. Previous ocean models assumed this fraction was constant. Here the variable solubility of Fe in aerosols and precipitation is parameterized with a two-step mechanism, the development of a sulfate coating followed by the dissolution of iron (hydr)oxide on the dust aerosols. The predicted soluble Fe fraction increases with transport time from the source region and with the corresponding decrease in dust concentration. The soluble fraction is ~1 percent near sources, but often 10--40 percent farther away producing a significant increase in soluble Fe deposition in remote ocean regions. Our results may require more rapid biological and physicochemical scavenging of Fe than used in current ocean models. We further suggest that increasing SO2 emission alone could have caused significant Fe fertilization in the modern northern hemisphere oceans.