To better understand the interaction of α-synuclein (αSyn) with lipid membranes, we carried out self-assembly molecular dynamics simulations of αSyn with monomeric and micellar sodium dodecyl sulfate (SDS), a widely used membrane mimic. We find that both electrostatic and hydrophobic forces contribute to the interactions of αSyn with SDS. In the presence of αSyn, our simulations suggest that SDS aggregates along the protein chain and forms small-size micelles at very early times. Aggregation is followed by formation of a collapsed protein-SDS micelle complex, which is consistent with experimental results. Finally, interaction of αSyn with preformed micelles induces alterations in the shape of the micelle, and the N-terminal helix (residues 3 through 37) tends to associate with micelles. Overall, our simulations provide an atomistic description of the early time scale αSyn-SDS interaction during the self-assembly of SDS into micelles.