Understanding the innate immune response to vaccination is critical in vaccine design. Here, we studied blood innate myeloid cells after first and second immunization of cynomolgus macaques with the modified vaccinia virus Ankara. The inflammation at the injection site was moderate and resolved faster after the boost. The blood concentration of inflammation markers increased after both injections but was lower after the boost. The numbers of neutrophils, monocytes, and dendritic cells were transiently affected by vaccination, but without any major difference between prime and boost. However, phenotyping deeper those cells with mass cytometry unveiled their high phenotypic diversity with subsets responding differently after each injection, some enriched only after the primary injection and others only after the boost. Actually, the composition in subphenotype already differed just before the boost as compared to just before the prime. Multivariate analysis identified the key features that contributed to these differences. Cell subpopulations best characterizing the post-boost response were more activated, with a stronger expression of markers involved in phagocytosis, antigen presentation, costimulation, chemotaxis, and inflammation. This study revisits innate immunity by demonstrating that, like adaptive immunity, innate myeloid responses differ after one or two immunizations.