Nanocomposite materials based on a starch matrix reinforced with very small amounts of multi-walled carbon nanotubes (MWCNTs) (from 0.005 wt% to 0.055 wt%) were developed. The material's dynamic-mechanical and water vapor permeability properties were investigated. An increasing trend of storage modulus (E′) and a decreasing trend of water vapor permeability (WVP) with filler content were observed at room temperature. For the composite with 0.055 wt% of filler, E′ value was about 100% higher and WVP value was almost 43% lower than the corresponding matrix values. MWCNTs were wrapped in an aqueous solution of a starch-iodine complex before their incorporation into the matrix, obtaining exceptionally well-dispersed nanotubes and optimizing interfacial adhesion. This excellent filler dispersion leads to the development of an important contact surface area with the matrix material, producing remarkable changes in the starch-rich phase glass transition temperature even in composites with very low filler contents. This transition is shifted towards higher temperatures with increasing content of nanotubes. So at room temperature, some composites are in the rubber zone while others, in the transition zone. Therefore, this change in the material glass transition temperature can be taken as responsible for the important improvements obtained in the composites WVP and E′ values for carbon nanotubes content as low as 0.05 wt%.