Chromium- and chromium-vanadium ledeburitic tool steels are extensively used in industry, for cold work tooling. The applications where abrasive wear is dominant such as fine-blanking, punching, cropping, shearing or trimming are typical examples. For these applications the steels must have high strength and hardness. On the other hand the tools have to withstand the chipping or cracking in real industrial processes. Hence, they should have at least acceptable fracture toughness. It is known that the strength and toughness are in strong conflict in most cases. The current paper deals with the possibility to balance between these properties, through application of different schedules of cryogenic treatments and tempering. The Vanadis 6 steel is used as a model material. Vacuum austenitized and gas quenched steel was subjected to cryogenic treatments at -75, -140, -196 or -269 °C, which was followed by different tempering. The fracture toughness of treated steel was determined by 10 × 10 × 55 mm prior fatigue pre-cracked specimens, by three-point bending tests. The testing of fracture toughness was complemented by careful microstructural investigations, hardness measurements and fractography. It has been established that cryogenic treatment makes it possible to simultaneously increase the hardness and toughness, albeit in relatively limited extent. The most promising way how to do it is the application of -140 °C for the cryogenic treatment followed by suitable tempering regime.