The work explores the federated data clustering problem. The primary goal is to perform k-means clustering of data distributed over multiple clients while preserving privacy during an exchange with the central server. Existing solutions to unsupervised federated data clustering are either computationally challenging or effective only in heterogeneous regimes, i.e., when the number of clusters per client (k_z) is less than the total number of clusters (k) (specifically, k_z ≤ unmapped: inline-formula unmapped: math unmapped: msqrt unmapped: mrow unmapped: mi k). Moreover, existing one-shot approaches assume that the information about k_z is available for each client. In this paper, we propose two multi-shot approaches which we call MFC and MFC_H, that perform well on both heterogeneous and non-heterogeneous regimes, i.e., are independent of the underlying client data distribution. Both MFC and MFC_H stand out as they do not rely on prior knowledge about k_z. We theoretically bound the closeness of the local centers obtained by MFC to that of the optimal global centers and prove that under some well-separability assumption, the centers will be close enough. MFC_H improvises MFC by only sharing a single cluster center from each client, thus ensuring more privacy. Our theoretical analysis shows that when at least O(k²log k) clients are involved, centers obtained by MFC_H will closely approximate optimal global centers. Experiments on synthetic and real-world datasets validate the proposed approaches’ efficacy showcasing lower objective costs in non-heterogeneous regimes while having comparable performance in heterogeneous regimes. In addition, as a byproduct MFC exhibits higher device-level fairness in terms of the individual objective cost compared to existing state-of-the-art algorithms. The code is publicly available at https://github.com/shivi98g/MFC.