Epitaxial heterostructures of two-dimensional (2D) halide perovskites offer a new platform for studying intriguing structural, optical, and electronic properties. However, difficulties with the stability of Pb- and Sn-based heterostructures have repeatedly slowed the progress. Recently, Pb-free halide double perovskites are gaining a lot of attention due to their superior stability and greater chemical diversity, but they have not been successfully incorporated into epitaxial heterostructures for further investigation. Here, we report epitaxial core-shell heterostructures via growing Pb-free double perovskites (involving combinations of Ag(I)-Bi(III), Ag-Sb, Ag-In, Na-Bi, Na-Sb, and Na-In) around Pb perovskite 2D crystals. Distinct from Pb-Pb and Pb-Sn perovskite heterostructures, growths of the Pb-free shell at 45° on the (100) surface of the lead perovskite core are observed in all Pb-free cases. The in-depth structural analysis carried out with electron diffraction unequivocally demonstrates the growth of the Pb-free shell along the [110] direction of the Pb perovskite, which is likely due to the relatively lower surface energy of the (110) surface. Furthermore, an investigation of anionic interdiffusion across heterostructure interfaces under the influence of heat was carried out. Interestingly, halide anion diffusion in the Pb-free 2D perovskites is found to be significantly suppressed as compared to Pb-based 2D perovskites. The great structural tunability and excellent stability of Pb-free perovskite heterostructures may find uses in electronic and optoelectronic devices in the near future.