Complete blood counts (CBCs) measure the abundance of individual immune cells, red blood cells, and related measures such as platelets in circulating blood. These measures can indicate the health status of an animal; thus, baseline circulating levels while an animal is healthy may be related to productive life, resilience, and production efficiency of cattle. The objective of this study was to determine the heritability of CBC traits and identify genomic regions that are associated with CBC measurements in lactating Holstein dairy cattle. Heritability of CBCs were estimated using a Bayes C0 model. The study population consisted of 388 cows with genotypes at roughly 75,000 markers and 16 different CBC phenotypes taken at one to three timepoints (n = 33, 131, 224 for 1, 2, and 3 timepoints, respectively). Heritabilities ranged from 0.00 ± 0.00 (red cell distribution width) to 0.68 ± 0.06 (lymphocytes). A total of 96 different 1 Mb windows were identified that explained more than 1% of the genetic variance for at least one CBC trait, with 10 windows explaining more than 1% of the genetic variance for two or more traits. Multiple genes in the identified regions have functions related to immune response, cell differentiation, anemia, and disease. Positional candidate genes include RAD52 motif-containing protein 1 (RDM1), which is correlated with the degree of immune infiltration of immune cells, and C-X-C motif chemokine ligand 12 (CXCL12), which is critically involved in neutrophil bone marrow storage and release regulation and enhances neutrophil migration. Since animal health impacts feed intake directly, understanding the genetics of CBCs may be useful to identify more disease resilient and feed efficient dairy cattle. Identification of genes responsible for variation in CBCs will also help identify the variability in how dairy cattle defend against illness and injury.