Introduction: Recent reviews on patients’ preferences towards attributes of oral anti-coagulant therapy have shown that preference for convenience of therapy is heterogeneous. In this study, we used a novel approach—latent class analysis (LCA)—to assess heterogeneity. Methods: We developed a health preference survey that consisted of 12 discrete choice questions. The following attributes of convenience were included: intake frequency; need for regular coagulation monitoring; diet or drug interactions; relation between medication and food intake; and pill type. Background questions about gender, age, current therapy [i.e., direct-acting oral anti-coagulant (DOAC) or vitamin K antagonist (VKA)], self-reported medication adherence, and pill burden were included. Mixed logit analysis (MLA) and LCA were performed. The scale-adjusted LCA model with two scale classes and four preference classes emerged as the model with the best fit and interpretability. Results: A total of 508 patients with non-valvular atrial fibrillation from five European countries (Germany, Italy, Spain, France, and the UK) were surveyed in August 2017. The most important attributes were need for monitoring (37%) and intake frequency (27%). Patient preferences were significantly influenced by country, gender, and current anti-coagulant therapy. Four different preference classes of patients were identified in the LCA. First, most patients (57%) were in the “no need for regular coagulation monitoring” class. Current DOAC users and patients who were the least adherent to therapy were more likely to prefer no coagulation monitoring. Second, 20% of patients were in the “balanced” class of patients. Current VKA users with moderate adherence were more likely to be in this class. Patients who reported the lowest adherence were most likely in the “once daily, interactions likely” class (16%). Fourth, current VKA users and highly adherent patients were most likely to prefer therapies with a need for regular coagulation monitoring (7%). Conclusions: This study demonstrated significant preference heterogeneity among patients with atrial fibrillation and linked these preferences to differences in background characteristics. Country of residence and currently prescribed therapy influenced patient preferences in both the MLA and LCA models.