We present a search for the flavor-changing neutral current decay B-s(0)->phi mu(+)mu(-) using about 0.45 fb(-1) of data collected in p (p) over bar collisions at root s=1.96 TeV with the D0 detector at the Fermilab Tevatron Collider. We find an upper limit on the branching ratio of this decay normalized to B-s(0)-> J/psi phi of B(B-s(0)->phi mu(+)mu(-))/B(B-s(0)-> J/psi phi)< 4.4x10(-3) at the 95% C.L. Using the central value of the world average branching fraction of B-s(0)-> J/psi phi, the limit corresponds to B(B-s(0)->phi mu(+)mu(-))< 4.1x10(-6) at the 95% C.L., the most stringent upper bound to date.