Cast Nafion-based composite membranes containing different amounts of organic, nanorod-shaped polyrotaxane were prepared and characterized, with the aim of improving the properties of polymer electrolyte membranes for direct methanol fuel cell applications. Polyrotaxane was prepared using the inclusion-complex reaction between ${alpha}$-cyclodextrin and poly(ethylene glycol) (PEG) of different molecular weights. The addition of polyrotaxane to Nafion changed the morphology and reduced the crystallinity. The conductivity of the composite membranes increased with increasing polyrotaxane content up to 5 wt%, but then decreased at higher polyrotaxane contents. Well-dispersed, organic polyrotaxane inside the membrane can provide a tortuous path for the transport of methanol, as the methanol permeability depends on the aspect ratio of polyrotaxane, which is controlled by the molecular weight of PEG. All of the Nafion-based, polyrotaxane composite membranes showed a higher selectivity parameter than the commercial Nafion films did.