Differentiated cells can be reprogrammed to the pluripotent state by overexpression of defined factors, and this process is profoundly influenced by epigenetic mechanisms including dynamic histone modifications. Changes in H3K4 methylation have been shown to be the predominant activating response in the early stage of cellular reprogramming. Mechanisms underlying such epigenetic priming, however, are not well understood. Here we show that the expression of the reprogramming factors (Yamanaka factors, Oct4, Sox2, Klf4 and Myc), especially Myc, directly promotes the expression of certain core subunits of the Set1/Mll family of H3K4 methyltransferase complexes. A dynamic recruitment of the Set1/Mll complexes largely, though not sufficiently in its own, explains the dynamics of the H3K4 methylation during cellular reprogramming. We then demonstrate that the core subunits of the Set1/Mll complexes physically interact with mainly Sox2 and Myc among the Yamanaka factors. We further show that Sox2 directly binds the Ash2l subunit in the Set1/Mll complexes and this binding is mediated by the HMG domain of Sox2. Functionally, we show that the Set1/Mll complex core subunits are required for efficient cellular reprogramming. We also show that Dpy30, one of the core subunits in the complexes, is required for the efficient target binding of the reprogramming factors. Interestingly, such requirement is not necessarily dependent on locus-specific H3K4 methylation. Our work provides a better understanding of how the reprogramming factors physically interact and functionally coordinate with a key group of epigenetic modulators to mediate transitions of the chromatin state involved in cellular reprogramming.