Psoriasis (Pso) is a chronic inflammatory skin disease, and up to 30% of Pso patients develop psoriatic arthritis (PsA), which can lead to irreversible joint damage. Early detection of PsA in Pso patients is crucial for timely treatment but difficult for dermatologists to implement. We, therefore, aimed to find disease-specific immune profiles, discriminating Pso from PsA patients, possibly facilitating the correct identification of Pso patients in need of referral to a rheumatology clinic. The phenotypes of peripheral blood immune cells of consecutive Pso and PsA patients were analyzed, and disease-specific immune profiles were identified via a machine learning approach. This approach resulted in a random forest classification model capable of distinguishing PsA from Pso (mean AUC = 0.95). Key PsA-classifying cell subsets selected included increased proportions of differentiated CD4+CD196+CD183-CD194+ and CD4+CD196-CD183-CD194+ T-cells and reduced proportions of CD196+ and CD197+ monocytes, memory CD4+ and CD8+ T-cell subsets and CD4+ regulatory T-cells. Within PsA, joint scores showed an association with memory CD8+CD45RA-CD197- effector T-cells and CD197+ monocytes. To conclude, through the integration of in-depth flow cytometry and machine learning, we identified an immune cell profile discriminating PsA from Pso. This immune profile may aid in timely diagnosing PsA in Pso.