The effect of carbon nanotubes (CNT), carbon nanofibers (CNF) and nano-sized silica (NS) on the frost durability of mortars was investigated. The test specimens were produced using Portland cement as binder and water to binder ratios of 0.5 and 0.33. CNT and CNF were added as water dispersion with superplasticizers. The NS was intermixed with micro silica and added as slurry. The frost durability was determined by a modified CIF method. The results showed that in the case of addition of nano-sized fibers a positive effect can be only found if the binder matrix is homogenous and dense. The combination of CNTs and NS resulted in the lack of any frost damage even after 180 freeze-thaw cycles.