Immune cells play a central role in early pregnancy establishment in cattle. We aimed to: (1) discover novel early-pregnancy-induced genes in peripheral blood mononuclear cells (PBMC); and (2) characterize the temporal pattern of early-pregnancy-induced transcription of select genes in PBMC and peripheral blood polymorphonuclear cells (PMN). Beef heifers were artificially inseminated on D0 and pregnancies were diagnosed on D28. On D10, 14, 16, 18, and 20, blood was collected for isolation of PBMC and PMN from heifers that were retrospectively classified as pregnant (P) or non-pregnant (NP). PBMC samples from D18 were submitted to RNAseq and 220 genes were differentially expressed between pregnant (P) and non-pregnant (NP) heifers. The temporal abundance of 20 transcripts was compared between P and NP, both in PBMC and PMN. In PBMC, pregnancy stimulated transcription of IFI6, RSAD2, IFI44, IFITM2, CLEC3B, OAS2, TNFSF13B, DMKN and LGALS3BP as early as D18. Expression of IFI44, RSAD2, OAS2, LGALS3BP, IFI6 and C1R in PMN was stimulated in the P group from D18. The novel early-pregnancy induced genes discovered in beef heifers will allow both the understanding of the role of immune cells during the pre-attachment period and the development of technologies to detect early pregnancies in beef cattle.