In this study, a hydrogenated nitrile rubber (HNBR)/tetrafluoroethylene, ethylene, and hexafluoropropylene terpolymer (EFEP) thermoplastic vulcanizate (TPV) is prepared by decreasing the cohesive energy density of HNBR, improving the compatibilization of two phases via dioctyl phthalate, and optimizing the cross-linking characteristics and the dynamic vulcanization process. The as-produced HNBR/EFEP TPV exhibits a fine dispersion of the HNBR phase within the EFEP matrix, resulting in good mechanical and rheological properties, high elasticity, excellent recyclability, high resistance to heat and oil, and good gas barrier properties. The morphological evolution of the HNBR/EFEP TPV indicates that the development of the microstructure is controlled by the in situ cross-linking and clustering of HNBR particles, with the subsequent breakup of the rubber particle aggregates. The enhancement of the compatibility of HNBR/EFEP and the effect of the shearing force led to a reduction in the size of HNBR particle agglomerates and an enhancement in the quantity of single HNBR particles during dynamic vulcanization.