Membrane-based gas separations are energy efficient processes; however, major challenges remain to develop high-performance membranes enabling replacement of conventional separation processes. Here, a new fluorinated MOF-based mixed-matrix membrane is reported, which is formed by incorporating the MOF crystals into selected polymers via a facile mixed-matrix approach. By finely controlling the molecular transport in the channels through MOF apertures and at the MOF-polymer interfaces, the resulting fluorinated MOF-based membranes exhibit excellent molecular sieving properties. We show that these materials significantly outperform state-of-the-art membranes for simultaneous removal of H2S and CO2 from natural gas—a challenging and economically-important application. The robust fluorinated MOFs, with tunable channel apertures provided by tuning the metal pillars and/or organic linker, pave a new avenue to efficient membrane separation processes that require precise discrimination of closely sized molecules.