The efficacy with which a range of nanotubes could reinforce a high density polyethylene (HDPE) matrix was investigated, in relation to nanotube diameter, purity, functionalization, alignment and nanotube bulk density. Composites were prepared by melt blending multiwall carbon nanotubes (MWNTs) with high density polyethylene (HDPE), followed by the injection molding of tensile specimens. At a 5 wt% loading, the most effective nanotubes were those of large diameter, received in an aligned form with low bulk density, producing a 66% increase in elastic modulus and a 69% improvement in yield stress. This was contradictory to theoretical mechanics calculations that predicted an increasing degree of reinforcement for nanotubes of reduced diameter. This difference was explained by the higher degree of dispersion observed in the composites with MWNTs of greater diameter.