Background With advancing age, the composition of leukocyte subpopulations in peripheral blood is known to change, but how this change differs between men and women and how it relates to frailty is poorly understood. Our aim in this exploratory study was to investigate whether frailty is associated with changes in immune cell subpopulations and whether this differs between men and women. Therefore, we performed in-depth immune cellular profiling by enumerating a total of 37 subpopulations of T cells, B cells, NK cells, monocytes, and neutrophils in peripheral blood of 289 elderly people between 60-87 years of age. Associations between frailty and each immune cell subpopulation were tested separately in men and women and were adjusted for age and CMV serostatus. In addition, a random forest algorithm was used to predict a participant's frailty score based on enumeration of immune cell subpopulations. Results In the association study, frailty was found to be associated with increased numbers of neutrophils in both men and in women. Frailer women, but not men, showed higher numbers of total and CD16(-)monocytes, and lower numbers of both CD56(+)T cells and late differentiated CD4(+)TemRA cells. The random forest algorithm confirmed all the findings of the association studies in men and women. In men, the predictive accuracy of the algorithm was too low (5.5%) to warrant additional conclusions on top of the ones derived from the association study. In women however, the predictive accuracy was higher (23.1%), additionally revealing that total T cell numbers and total lymphocyte numbers also contribute in predicting frailty. Conclusions In-depth immune cellular profiling revealed consistent associations of frailty with elevated numbers of myeloid cell subpopulations in both men and women. Furthermore, additional associations were found between frailty and lower numbers of some T cell subpopulations, in women only. Thus, our study indicates sex-specific associations of immune subpopulations with frailty. We hope that our study will prompt further investigation into the sex-specific immune mechanisms associated with the development of frailty.