In this work, the effect of the addition of multi-walled carbon nanotubes (MWCNTs) on the mechanical properties and durability of ultra high strength concrete (UHSC) is reported. First, the MWCNTs were dispersed by a nano sand-mill in the presence of a surfactant in water. The UHSC specimens were prepared with various amounts of MWCNTs, ranging from 0% to 0.15% by weight of cement (bwoc). Results indicated that use of an optimal percentage of MWCNTs (0.05% bwoc) caused a 4.63% increase in compressive strength and a 24.0% decrease in chloride diffusion coefficient of UHSC at 28 days curing. Moreover, the addition of MWCNTs also improved the flexural strength and deformation ability. Furthermore, a field-emission scanning electron microscopy (FE-SEM) was used to observe the dispersion of MWCNTs in the cement matrix and morphology of the hardened cement paste containing MWCNTs. FE-SEM observation revealed that MWCNTs were well dispersed in the matrix and no agglomerate was found and the reinforcing effect of MWCNTs on UHSC was thought to be pulling out and microcrack bridging of MWCNTs, which transferred the load in tension.