We calculate the excess chemical potential of methane in aqueous electrolyte solutions of NaCl using Monte Carlo computer simulations. In a recent work [Docherty et al. J. Chem. Phys.2006, 125, 074510], we presented a new potential model for methane in water which is capable of describing accurately the excess chemical potential of methane in pure water over a range of temperatures, a quantity that can be related to the solubility and which is commonly used to study the hydrophobic effect. Here, we use the same potential model for the water-methane interactions and investigate the effect of added salt on the chemical potential of methane in the solution. The methane molecules are modeled as single Lennard-Jones (LJ) interaction sites, and the water molecules are modeled with the TIP4P/2005 model. A correcting factor of chi = 1.07 for the energetic Berthelot (geometric) combining rule of the methane-water interaction is also used, which mimics the polarization of methane in water. We consider NaCl as the salt and treat the ions with the Smith and Dang model (i.e., as charged LJ interaction sites). Ion-water, ion-ion, and ion-methane interactions are treated using Lorentz-Berthelot combining rules. In addition, the Coulombic potential is used to model charge-charge interactions which are calculated using the Ewald sum. We have carried out isobaric-isothermal (NpT) simulations to determine the equilibrium densities of the solutions. The simulation data is in excellent agreement with experimental densities of aqueous NaCl solutions of different concentration. Hydration numbers are also obtained and found to be in agreement with reported data. Canonical (NVT) simulations at the averaged densities are then performed using the Widom test-particle insertion method to obtain the excess chemical potential of methane in the saline solutions. An increase in the chemical potential of methane, corresponding to a salting out effect, is observed when salt is added to the solution. We investigate different concentrations and ion sizes. An overprediction of the salting out effect as compared with experimental data is observed, which we believe is due to the polarizing effect of the ions in the solution, which is not taken into account by the model. We also find a direct correlation between the increase in the chemical potential and the packing fraction of the solution and argue that the main cause of the observed salting out effect (as represented by an increase in the excess chemical potential) is the increase in the packing fraction of the solutions due to the added salt. Together, with this, we put forward an argument toward explaining the anomalous Hofmeister effect of Li+.