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.4
pb-1 of data collected at the Collider Detector at Fermilab (CDF).  We find
two candidate events for this decay, which is consistent with the background
estimate, and set a preliminary upper limit on the branching fraction of
B(B_s --> mu+ mu- phi) < 4.2 . 10-5 at a 90% confidence level.