Nanocrystalline tungsten-copper composites can favorably combine the outstanding material properties of both elements. This work investigates tungsten-copper composites fabricated from elemental powders with 80 wt.% tungsten and either copper or α-brass containing 20 wt.% zinc, respectively. Moreover, high-pressure torsion is used to compact the powders, strengthen the resulting composite by grain refinement, and tailor the grain-size in the nanocrystalline regime by varying the deformation temperature between RT, 400°C and 550°C, resulting in grain-sizes of 9 nm 14 nm and 28 nm, respectively. Hardness measurements revealed a transition from normal to inverse Hall-Petch behavior for grain-sizes below 11 nm. To examine the fracture properties, micro-cantilever bending beams with a cross-section of 10x10 µm2 were fabricated. Evaluation of these experiments indicated a fracture toughness of 3 MPam. The slight decrease of fracture toughness between a grain-size of 9 nm to 14 nm indicates a reduction of the grain boundary cohesion strength. The grain-size increase to 28 nm reversed the trend in fracture toughness and raised it to 3.4 MPam, which points to activating additional deformation mechanisms, such as dislocation-accumulation and twinning. Additionally, alloying with zinc raised the composites strength and retained the composites fracture toughness, benefiting the damage tolerance.