Simple SUSY GUT models based on the gauge group SO(10) require t-b-\tau Yukawa coupling unification, in addition to gauge coupling and matter unification. The Yukawa coupling unification places strong constraints on the expected superparticle mass spectrum, with scalar masses \sim 10 TeV while gluino masses are much lighter: in the 300--500 GeV range. The very heavy squarks suppress negative interference in the q\bar{q}\to\tg\tg cross section, leading to a large enhancement in production rates. The gluinos decay almost always via three-body modes into a pair of b-quarks, so we expect at least four b-jets per signal event. We investigate the capability of Fermilab Tevatron collider experiments to detect gluino pair production in Yukawa-unified SUSY. By requiring events with large missing E_T and \ge 2 or 3 tagged b-jets, we find a 5\sigma reach in excess of m_{\tg}\sim 400 GeV for 5 fb^{-1} of data. This range in m_{\tg} is much further than the conventional Tevatron SUSY reach, and should cut a significant swath through the most favored region of parameter space for Yukawa-unified SUSY models.