Exposure to ambient air pollution during pregnancy has been associated with an increased risk of preeclampsia (PE). Some suggested mechanisms behind this association are changes in placental DNA methylation and gene expression. The objective of this study was to identify how early pregnancy exposure to ambient nitrogen oxides (NOx) among PE cases and normotensive controls influence DNA methylation (EPIC array) and gene expression (RNA-seq). The study included placentas from 111 women (29 PE cases/82 controls) in Scania, Sweden. First-trimester NOx exposure was assessed at the participants’ residence using a dispersion model and categorized via median split into high or low NOx. Placental gestational epigenetic age was derived from the DNA methylation data. We identified six differentially methylated positions (DMPs, q < 0.05) comparing controls with low NOx vs. cases with high NOx and 14 DMPs comparing cases and controls with high NOx. Placentas with female fetuses showed more DMPs (N = 309) than male-derived placentas (N = 1). Placentas from PE cases with high NOx demonstrated gestational age deceleration compared to controls with low NOx (p = 0.034). No differentially expressed genes (DEGs, q < 0.05) were found. In conclusion, early pregnancy exposure to NOx affected placental DNA methylation in PE, resulting in placental immaturity and showing sexual dimorphism.