  In this letter, we consider the constraints imposed by the recent measurement
of B_s - bar B_s mixing on the new physics contribution to the rare decay B_s
--> mu+ mu-. New physics in the form vector and axial-vector couplings is
already severely constrained by the data on B --> (K,K*) mu+ mu-. Here, we show
that B_s - bar B_s mixing data, together with the data on K0 - bar K0 mixing
and K_L --> mu+ mu- decay rate, strongly constrain the scalar-pseudoscalar
contribution to B_s --> mu+ mu-. We conclude that new physics can at best lead
to a factor of 2 increase in the branching ratio of B_s --> mu+ mu- compared to
its Standard Model expectation.
