Due to their abundance in the blood, low RNA content, and short lifespan, neutrophils have been classically considered to be one homogenous pool. However, recent work has found that mature neutrophils and neutrophil progenitors are composed of unique subsets exhibiting context-dependent functions. In this study, we ask if neutrophil heterogeneity is associated with melanoma incidence and/or disease stage. Using mass cytometry, we profiled melanoma patient blood for unique cell surface markers among neutrophils. Markers were tested for their predictiveness using flow cytometry data and random forest machine learning. We identified CD79b neutrophils (CD3 CD56 CD19 Siglec8 CD203c CD86 CD66b CD79b ) that are normally restricted to the bone marrow in healthy humans but appear in the blood of subjects with early-stage melanoma. Further, we found CD79b neutrophils present in tumors of subjects with head and neck cancer. AI-mediated machine learning analysis of neutrophils from subjects with melanoma confirmed that CD79b expression among peripheral blood neutrophils is highly important in identifying melanoma incidence. We noted that CD79b neutrophils possessed a neutrophilic appearance but have transcriptional and surface-marker phenotypes reminiscent of B cells. Compared to remaining blood neutrophils, CD79b neutrophils are primed for NETosis, express higher levels of antigen presentation-related proteins, and have an increased capacity for phagocytosis. Our work suggests that CD79b neutrophils are associated with early-stage melanoma.