Cellulose nitrate (CN) composite membranes, containing cobalt porphyrin (CoP) complexes self-assembled within nanometer-sized rhenium clusters (ReCoP), have been prepared and their oxygen and nitrogen gas permeabilities were analyzed. The solubility of ReCoP and the characteristics of the corresponding composite membranes were analyzed using a Cahn microbalance, FT-IR spectroscopy, wide-angle X-ray scattering, and differential scanning calorimetry. The nitrogen permeability through the CN composite membranes decreased upon addition of ReCoP and CoP, which implies that the presence of these oxygen carrier complexes affects the structure of the polymer matrix. The oxygen permeability through the composite membranes containing small quantities of ReCoP decreased, but it increased upon increasing the concentration. The oxygen gas transport was affected by the matrix at low ReCoP concentrations, but higher concentrations of ReCoP increased the oxygen permeability as a result of its reversible and specific interactions with oxygen, effectively realizing ReCoP carrier-mediated oxygen transport.