A search for direct production of scalar bottom quarks (b˜) is performed with 310 pb−1 of data collected by the D0 experiment in pp¯ collisions at s=1.96 TeV at the Fermilab Tevatron Collider. The topology analyzed consists of two b jets and an imbalance in transverse momentum due to undetected neutralinos (χ˜10), with χ˜10 assumed to be the lightest supersymmetric particle. We find the data consistent with standard model expectations, and set a 95% C.L. exclusion domain in the (mb˜, mχ˜10) mass plane, improving significantly upon the results from run I of the Tevatron.Received 7 August 2006DOI:https://doi.org/10.1103/PhysRevLett.97.171806©2006 American Physical Society