Highly-stable carbon clusters on transition metal substrates play an important role in the bottom-up approaches for synthesizing graphene quantum dots, graphene nanoribbons, and novel graphene nanostructures. Here, the discovery of a series of magic-sized carbon clusters on different transition metal substrates is reported. Careful analyses reveal that the symmetry matching between the cluster and the substrate, the interaction between cluster edge carbon atoms and the substrate, and the location and orientation of the cluster on the substrate play key roles in stabilizing the new family of magic-sized carbon clusters. The identified magic-sized carbon clusters are thermodynamically and kinetically stable and may serve as the nucleation centers in the synthesis of other graphene nanostructures. These findings will greatly enrich the species of highly-stable carbon clusters on transition metal substrates and paving the road toward the synthesis route of other graphene nanostructures