Here, we report for the first time the fabrication of polymer/selective- flake nanocomposite membranes which can, in principle, be scaled down to submicrometer structures. A layered aluminophosphate with a porous net layer is used as a selective phase and a polyimide as a continuous phase. The microstructures of the nanocomposite membranes are investigated using various characterization techniques including X-ray diffraction, NMR, transmission electron microscopy, small-angle neutron scattering, and dynamic mechanical thermal analysis. Nanocomposite membranes with 10 wt % layered aluminophosphate show substantial enhancement in performance with oxygen selectivity over nitrogen as high as 8.9 (as compared to 3.6 for pure polymer) and carbon dioxide selectivity over methane as high as 40.9 (as compared to 13.4 for pure polymer) in room-temperature permeation measurements. This improved performance, along with permeability estimation through the aluminophosphate layers with a semiempirical model, suggests that the layered aluminophosphate plays a role as a molecular sieve favoring smaller molecules.