Acyl-protein thioesterase-1 (APT1) and APT2 are cytosolic enzymes that catalyze depalmitoylation of membrane-anchored, palmitoylated H-Ras and growth-associated protein-43 (GAP-43), respectively. However, the mechanism(s) of cytosol-membrane shuttling of APT1 and APT2, required for depalmitoylating their substrates H-Ras and GAP-43, respectively, remained largely unknown. Here, we report that both APT1 and APT2 undergo palmitoylation on Cys-2. Moreover, blocking palmitoylation adversely affects membrane localization of both APT1 and APT2 and that of their substrates. We also demonstrate that APT1 not only catalyzes its own depalmitoylation but also that of APT2 promoting dynamic palmitoylation (palmitoylation-depalmitoylation) of both thioesterases. Furthermore, shRNA suppression of APT1 expression or inhibition of its thioesterase activity by palmostatin B markedly increased membrane localization of APT2, and shRNA suppression of APT2 had virtually no effect on membrane localization of APT1. In addition, mutagenesis of the active site Ser residue to Ala (S119A), which renders catalytic inactivation of APT1, also increased its membrane localization. Taken together, our findings provide insight into a novel mechanism by which dynamic palmitoylation links cytosol-membrane trafficking of APT1 and APT2 with that of their substrates, facilitating steady-state membrane localization and function of both.