Carbon fibre-reinforced ultra-high temperature ceramics (UHTCs) are considered a class of promising materials for several applications, the most appealing ones being in the aerospace sector. Reinforcement is necessary to overcome the brittleness and low thermal shock resistance of ceramics and is often provided through the addition of carbon fibres or other carbon-based phases, such as nanotubes, graphene, and graphite. The present work is focused on the toughening of UHTCs through incorporation of 30−50 vol% thin, ordered graphite layers from conventional filter paper followed by hot pressing sintering. Cellulose filter paper was selected because it undergoes thermolysis with no melting stage forming a strong carbonaceous residue that can be used as toughener. Microstructure and mechanical properties of toughened composites were compared to those of other materials reinforced with short carbon fibres and the effect of different distribution of graphite was studied. Addition of graphite allowed toughness to be increased from 3−4 MPa·m^1/2 (for un-reinforced materials) to 5.1−5.5 MPa·m^1/2, similar to results obtained with short fibre reinforcement. The high-temperature properties, such as strength and toughness as well as oxidation resistance at 1500 ℃, were also examined.