The origin of ultra-low friction exhibited by heterogeneous junctions of graphene and hexagonal boron nitride (h-BN) is revealed. For aligned interfaces, we identify a characteristic contact size, below which the junction behaves like its homogeneous counterparts with friction forces that grow linearly with the contact area. Superlubricity sets in due to the progressive appearance of Moiré patterns resulting in a collective stick-slip motion of the elevated super-structure ridges that turns into smooth soliton-like gliding with increasing contact size. Incommensurability effects are enhanced in misaligned contacts, where the friction coefficients further drop by orders of magnitude. Our fully atomistic simulations show that the superlubric regime in graphene/h-BN heterostructures persists up to significantly higher loads compared to the well-studied twisted homogeneous graphene interface. This indicates the potential of achieving robust superlubricity in practical applications using two-dimensional layered materials heterojunctions.