\(K\)-medoids clustering is among the most popular methods for cluster analysis, but it carries several assumptions about the nature of the latent clusters. In this paper, we introduce the Convex Fuzzy k-Medoids (CFKM) model, whose underlying formulation not only relaxes the assumption that objects must be assigned entirely to one and only one medoid, but also that medoids must be assigned entirely to one and only one cluster. Moreover, due to its convexity, CFKM resolution is completely robust to initialization. We compare our model with two fuzzy k-medoids clustering models found in the literature: the Fuzzy k-Medoids (FKM) and the Fuzzy Clustering with Multi-Medoids (FMMdd), both solved approximately by heuristics because of their hard computational complexity. Our experiments in synthesized and real-world data sets reveal that our model can uniquely discover important aspects of clustered data which are inherently fuzzy in nature, besides being more robust regarding the hyperparameters of the fuzzy clustering task.