We have performed atomistic molecular dynamics simulations of an anionic sodium dodecyl sulfate (SDS) micelle and a nonionic poly(ethylene oxide) (PEO) polymer in aqueous solution. The micelle consisted of 60 surfactant molecules, and the polymer chain lengths varied from 20 to 40 monomers. The force field parameters for PEO were adjusted by using 1,2-dimethoxymethane (DME) as a model compound and matching its hydration enthalpy and conformational behavior to experiment. Excellent agreement with previous experimental and simulation work was obtained through these modifications. The simulated scaling behavior of the PEO radius of gyration was also in close agreement with experimental results. The SDS-PEO simulations show that the polymer resides on the micelle surface and at the hydrocarbon-water interface, leading to a selective reduction in the hydrophobic contribution to the solvent-accessible surface area of the micelle. The association is mainly driven by hydrophobic interactions between the polymer and surfactant tails, while the interaction between the polymer and sulfate headgroups on the micelle surface is weak. The 40-monomer chain is mostly wrapped around the micelle, and nearly 90% of the monomers are adsorbed at low PEO concentration. Simulations were also performed with multiple 20-monomer chains, and gradual addition of polymer indicates that about 120 monomers are required to saturate the micelle surface. The stoichiometry of the resulting complex is in close agreement with experimental results, and the commonly accepted "beaded necklace" structure of the SDS-PEO complex is recovered by our simulations.