The cement industry is one of the most polluting industries globally, due to the high amount of CO₂ emissions generated during production. Improving the sustainability of cement production is thus vital. Waste paper is also a big problem for many societies, especially in developed countries, where the use of board and paper increases almost every day. This work examines the possibility of using incinerated waste paper ash (IWPA) and non-incinerated waste paper (NIWP) as a partial replacement for cement (by weight) in mortar mixtures. For non-incinerated waste paper, the tested replacement levels were 1%, 1.5%, 2.5% and 3.5%, while for incinerated waste paper, the replacement levels were 2.5%, 5%, 7.5%, and 10%. An additional mix without any replacement was also cast for comparison purposes. The fresh and hardened properties of mortar were assessed using flow rate, compressive strength, direct tensile strength, water absorption, and dry density tests, and two test ages (7 and 28 days) were considered for the compressive and tensile strength tests, though water absorption and density tests were undertaken at 28 days only. The results showed that the presence of waste paper (incinerated or non-incinerated) reduced the flow rate of fresh mortar as compared with the reference mix. It was also found that, for the NIWP mixtures, 1% replacement of cement was the most efficient percentage; this increased the compressive strength by 16% and the direct tensile strength by 19% at 28 days of age. For the IWPA mixes, the results showed that the best replacement ratio was 5%, where the compressive strength and direct tensile strength were improved by 10% and 11% at 28 days, respectively. These 1% NIWP and 5% IWPA mixtures gave similar water absorption of 7% to the reference mix.