Polymer/carbon nanotube (CNT) composites are one of the most perspective advanced materials developed in recent years. The properties of CNT-reinforced polymer composites, however, strongly depend on structural aspects of the nanostructured filler and on its dispersion quality in a polymer matrix. Consequently, this research was devoted to the investigation of multiwalled-CNT-modified poly(vinyl acetate) (PVAc) composites with respect to the mechanical property dependence on some structural characteristics of CNTs. PVAc/CNT nanocomposites were obtained with a solution casting technique. The amount of CNTs was changed from 0.01 up to 2 wt %. The stress–strain characteristics of PVAc/CNT nanocomposites clearly revealed remarkable reinforcing effects of the CNT additions already at 0.01 wt %. At this CNT concentration, the elastic modulus (E) and tensile yield stress increased by 12.5 and 60%, respectively. Special attention was paid to the change of E with respect to some structural characteristics of CNTs. A corresponding mathematical model for the prediction of the elastic properties of CNT polymer nanocomposites is proposed, showing that elastic constants of the nanocomposites largely depend on the agglomeration of CNTs.