We present a search for the flavor-changing neutral current decay
B_s --> mu+ mu- phi in p anti-p collisions at s**(1/2) = 1.8 TeV, using 91 pb-1
of data collected at the Collider Detector at Fermilab (CDF). We find two
candidate events for this decay, which are consistent with the background
estimate of one event, and set an upper limit on the branching fraction of
B(B_s --> mu+ mu- phi) < 6.7 . 10-5 at a 95% confidence level. This is
the first limit on the branching fraction of this decay.