Laser cooling by anti-Stokes fluorescence is a technology to realize all-solid-state optical cryocoolers. We grew Yb3+-doped KY3F10 (Yb:KYF) crystals as novel laser cooling media and compare their cooling performance to Yb3+-doped LiYF4 (Yb:YLF) crystals also grown in our institute. We present temperature-dependent absorption and emission cross sections as well as the fluorescence lifetime of Yb:KYF, and calculate its material figure-of-merit for laser cooling. Yb:KYF exhibits a higher figure-of-merit than Yb:YLF at temperatures below 200 K. This is because, in contrast to Yb:YLF, the excitation transition from the second-highest Stark level of the ground state is best-suited for cryogenic cooling in Yb:KYF. Thus, it has the potential to achieve unprecedentedly low temperatures below the boiling point of liquid nitrogen. In this work, we observe the first laser cooling of Yb:KYF, and obtain a background absorption coefficient of ∼10-4 cm-1, which is among the lowest ever reported for Yb3+-doped fluoride crystals. A simple model calculation predicts that our Yb:KYF and Yb:YLF crystals can potentially be cooled down to ≈100 K in a high-power cooling setup. Our Yb:KYF crystals still leave room for further improvement through the optimization of the growth process and the use of purer raw materials.