We present the results of a search for the flavor-changing neutral current decay B0s→μ+μ− using a data set with integrated luminosity of 240 pb−1 of p¯p collisions at √s=1.96 TeV collected with the D0 detector in run II of the Fermilab Tevatron collider. We find the upper limit on the branching fraction to be B(B0s→μ+μ−)≤5.0×10−7 at the 95% C.L. assuming no contributions from the decay B0d→μ+μ− in the signal region. This limit is the most stringent upper bound on the branching fraction B0s→μ+μ− to date.Received 15 October 2004DOI:https://doi.org/10.1103/PhysRevLett.94.071802©2005 American Physical Society