The hydrophobic interaction between two methane molecules in salt-free and high salt-containing aqueous solutions and the structure in such solutions have been investigated using an atomistic model solved by Monte Carlo simulations. Monovalent salt representing NaCl and divalent salt with the same nonelectrostatic properties as the monovalent salt have been used to examine the influence of the valence of the salt species. In salt-free solution the effective interaction between the two methane molecules displayed a global minimum at close contact of the two methane molecules and a solvent-separated secondary minimum. In 3 and 5 M monovalent salt solution the potential of mean force became slightly more attractive, and in a 3 M divalent salt solution the attraction became considerably stronger. The structure of the aqueous solutions was determined by radial distribution functions and angular probability functions. The distortion of the native water structure increased with ion valence. The increase of the hydrophobic attraction was associated with (i) a breakdown of the tetrahedral structure formed by neighboring water molecules and of the hydrogen bonds between them and (i) the concomitant increase of the solution density.