Due to high density of native defects, the prototypical topological insulator (TI), Bi$_2$Se$_3$, is naturally n-type. Although Bi$_2$Se$_3$ can be converted into p-type by substituting 2+ ions for Bi, only light elements such as Ca have been so far effective as the compensation dopant. Considering that strong spin-orbit coupling (SOC) is essential for the topological surface states, a light element is undesirable as a dopant, because it weakens the strength of SOC. In this sense, Pb, which is the heaviest 2+ ion, located right next to Bi in the periodic table, is the most ideal p-type dopant for Bi$_2$Se$_3$. However, Pb-doping has so far failed to achieve p-type Bi$_2$Se$_3$ not only in thin films but also in bulk crystals. Here, by utilizing an interface engineering scheme, we have achieved the first Pb-doped p-type Bi$_2$Se$_3$ thin films. Furthermore, at heavy Pb-doping, the mobility turns out to be substantially higher than that of Ca-doped samples, indicating that Pb is a less disruptive dopant than Ca. With this SOC-preserving counter-doping scheme, it is now possible to fabricate Bi$_2$Se$_3$ samples with tunable Fermi levels without compromising their topological properties.