The atomic-scale friction of the fluorographene (FG)/MoS2 heterostructure is investigated using first-principles calculations. Due to the intrinsic lattice mismatch and formation of periodic Moiré patterns, the potential energy surface of the FG/MoS2 heterostructure is ultrasmooth and the interlayer shear strength is reduced by nearly two orders of magnitude, compared with both FG/FG and MoS2/MoS2 bilayers, entering the superlubricity regime. The size dependency of superlubricity is revealed as being based on the relationship between the emergence of Moiré patterns and the lattice mismatch ratio for heterostructures.