Previously we showed that extravillous cytotrophoblast (EVT) outgrowth and migration on a collagen gel explant model were affected by exposure to decidual natural killer cells (dNK). This study investigates the molecular causes behind this phenomenon. Genome wide DNA methylation of exposed and unexposed EVT was assessed using the Illumina Infinium HumanMethylation450 BeadChip array (450 K array). We identified 444 differentially methylated CpG loci in dNK-treated EVT compared with medium control (P < 0.05). The genes associated with these loci had critical biological roles in cellular development, cellular growth and proliferation, cell signaling, cellular assembly and organization by Ingenuity Pathway Analysis (IPA). Furthermore, 23 mobility-related genes were identified by IPA from dNK-treated EVT. Among these genes, CLDN4 (encoding claudin-4) and FUT4 (encoding fucosyltransferase IV) were chosen for follow-up studies because of their biological relevance from research on tumor cells. The results showed that the mRNA and protein expressions of both CLDN4 and FUT4 in dNK-treated EVT were significantly reduced compared with control (P < 0.01 for both CLDN4 and FUT4 mRNA expression; P < 0.001 for CLDN4 and P < 0.01 for FUT4 protein expression), and were inversely correlated with DNA methylation. Knocking down CLDN4 and FUT4 by small interfering RNA reduced trophoblast invasion, possibly through the altered matrix metalloproteinase (MMP)-2 and/or MMP-9 expression and activity. Taken together, dNK alter EVT mobility at least partially in association with an alteration of DNA methylation profile. Hypermethylation of CLDN4 and FUT4 reduces protein expression. CLDN4 and FUT4 are representative genes that participate in modulating trophoblast mobility.