In the last years, we have witnessed an unstoppable growth of data created, captured, copied, and consumed globally by more and more devices. The demand for such an increasing amount of information to be processed led to research towards higher computational power systems and specialized algorithms. Among them, quantum computing is a promising paradigm based on quantum theory for performing fast computations. Quantum algorithms are expected to surpass their classical counterparts in terms of computational complexity for certain kinds of tasks, and machine learning is one of them, so the subfield of Quantum Machine Learning is one of the most promising. In this work, we design a hybrid quantum algorithm for k-Means. The main idea of our algorithm is to compute in a quantum way the distance between pairs of records in the input dataset. We show that our quantum algorithm could be, in principle, more efficient than the classical k-Means, yet obtain comparable clustering results.