Catalytic systems based on sub-nanoclusters deposited over different supports are promising for very relevant chemical transformations such as many electrocatalytic processes as the ORR. These systems have been demonstrated to be very fluxional, as they are able to change shape and interconvert between each other either alone or in the presence of adsorbates. In addition, an accurate representation of their catalytic activity requires the consideration of ensemble effects and not a single structure alone. In this sense, a reliable theoretical methodology should assure an accurate and extensive exploration of the potential energy surface to include all the relevant structures and with correct relative energies. In this context, we applied DFT in conjunction with global optimization techniques to obtain and analyze the characteristics of the many local minima of Pt6 sub-nanoclusters over a carbon-based support (graphene)—a system with electrocatalytic relevance. We also analyzed the magn