G protein coupled receptors (GPCRs) allow for the transmission of signals across biological membranes. For a number of GPCRs, this signaling was shown to be coupled to prior dimerization of the receptor. The chemokine receptor type 4 (CXCR4) was reported before to form dimers and their functionality was shown to depend on membrane cholesterol. Here, we address the dimerization pattern of CXCR4 in pure phospholipid bilayers and in cholesterol-rich membranes. Using ensembles of molecular dynamics simulations, we show that CXCR4 dimerizes promiscuously in phospholipid membranes. Addition of cholesterol dramatically affects the dimerization pattern: cholesterol binding largely abolishes the preferred dimer motif observed for pure phospholipid bilayers formed mainly by transmembrane helices 1 and 7 (TM1/TM5-7) at the dimer interface. In turn, the symmetric TM3,4/TM3,4 interface is enabled first by intercalating cholesterol molecules. These data provide a molecular basis for the modulation of GPCR activity by its lipid environment.