At cryogenic temperatures thermoset polymers suffer from low fracture toughness. Herein, we present a strengthening and toughening technique for cryogenic applications using cupric oxide (CuO) nanorods. These nanorods are synthesized via a hydrothermal reaction to give an average length of 1.64 and a diameter of 270 nm. They exhibit a low coefficient of thermal expansion (CTE) at cryogenic temperatures, due to the magnetostriction effect. Epoxy nanocomposites containing up to 8 wt% of CuO nanorods were investigated. Both the tensile strength and the fracture energy were found to increase with CuO nanorods content up to 4 wt%, showing improvements of 18% and 133% respectively at room temperature, and of 21% and 261% at −196 °C. Current theoretical models were shown to account for the experimentally measured values of both strength and toughness at room temperature, but to significantly underestimate the observed values at −196 °C. However, modifications of these models to include thermal residual stresses generated by the CTE mismatch are proposed that lead to good agreement with the measured values. The technique to strengthen and toughen epoxy using CuO nanorods and the modified theories provide potential for designing and optimising multi-scale fibre composites for cryogenic applications such as cryogenic fuel tanks.