7 pages, 2 figures, LaTeX, to be submitted to Physical Review Letters - D0 ; We present a search for the flavor-changing neutral current decay B0_s -> phi mu+ mu- using about 0.45 fb^-1 of data collected in p \bar p collisions at sqrt{s} =1.96 TeV with the D{Ø}detector at the Fermilab Tevatron Collider. We find an upper limit on the branching ratio of this decay normalized to B0_s -> J/psi phi of B(B0_s -> phi mu+ mu-)/B(B0_s -> J/psi phi) J/psi phi, the limit corresponds to B(B0_s -> phi mu+ mu-)