In this work, nanofibrillated cellulose (NFC) has been evaluated as a potential reinforcement for cement mortar composites. Two types of vegetable fibres with different composition and properties (cellulose content and microfibrillar angle), sisal, and cotton linters pulps, were initially characterised in order to assess their reinforcing capability. Sisal pulp was found to be most suitable as reinforcement for the brittle cementitious matrix. Nanofibrillated cellulose was produced by the application of a high intensity refining process of the sisal pulp. It was found that 6 hours of refining time was required to obtain the desired nanofibrillation of the fibers. Cement mortar composites reinforced with both the sisal fibres and the nanofibrillated cellulose were prepared, and the mechanical properties were determined under flexural tests. The cement mortar composites reinforced with the nanofibrillated cellulose exhibited enhanced flexural properties, but lower values of fracture energy, than the ones reinforced with the conventional sisal fibres.