Mechanically-robust nanocomposite membranes have been developed via crosslinking chemistry and electrospinning technique based on the rational selection of dispersed phase materials with high Young’s modulus (i.e., graphene and multiwalled carbon nanotubes) and Cassie-Baxter design and used for oil and water separation. Proper selection of dispersed phase materials can enhance the stiffness of nanocomposite fiber membranes while their length has to be larger than their critical length. Chemical modification of the dispersed phase materials with fluorochemcials and their induced roughness were critical to achieve superhydrophobocity. Surface analytic tools including goniometer, X-ray photoelectron spectroscopy (XPS), Fourier transform infrared (FTIR) spectroscopy, Raman spectroscopy, atomic force microscopy (AFM) and scanning electron microscope (SEM) were applied to characterize the superhydrophobic nanocomposite membranes. An AFM-based nanoindentation technique was used to measure quantitativly the stiffness of the nanocomposite membranes for local region and whole composites, compared with the results by a tensile test technique. Thermogravimetric analysis (TGA) and differential scanning calorimetry (DSC) techniques were used to confirm composition and formation of nanocomposite membranes. These membranes demonstrated excellent oil/water separation. This work has potential application in the field of water purification and remediation.