New physics contributions to B_s-\bar{B}_s mixing can be parametrized by the size (r_s^2) and the phase (2\theta_s) of the total mixing amplitude relative to the Standard Model amplitude. The phase has so far been unconstrained. Combining two recent measurements, that of the mass difference (\Delta M_s) by CDF and that of the semileptonic CP asymmetry (A_{SL}) by D0, we obtain the first constraint on the semileptonic CP asymmetry in B_s decays, A_{SL}^s=-0.013 \pm 0.015. The error on A_{SL}^s should still be reduced by a factor of order four to have a sensitive probe of the phase, yet the low central value is such that large positive values of sin(2\theta_s) are disfavored.