They cannot be observed via microscopic experimental techniques due to their small size, yet there is also a lack of atomistic simulation models able to describe spontaneous nanodomain formation in sufficiently simple but biologically relevant complex membranes. Here we use atomistic simulations to consider a binary mixture of saturated dipalmitoylphosphatidylcholine and cholesterol — the “minimal standard” for nanodomain formation. The simulations reveal how cholesterol drives the formation of fluid cholesterol-rich nanodomains hosting hexagonally packed cholesterol-poor lipid nanoclusters, both of which show registration between the membrane leaflets. The complex nanodomain substructure forms when cholesterol positions itself in the domain boundary region. Here cholesterol can also readily flip–flop across the membrane. Most importantly, replacing cholesterol with a sterol characterized by a less asymmetric ring region impairs the emergence of nanodomains. The model considered explains a plethora of controversial experimental results and provides an excellent basis for further computational studies on nanodomains. Furthermore, the results highlight the role of cholesterol as a key player in the modulation of nanodomains for membrane protein function.