We report results from a search for the decay B0s→μ+μ− using 1.3 fb−1 of p¯p collisions at √s=1.96 TeV collected by the D0 experiment at the Fermilab Tevatron Collider. We find two candidate events, consistent with the expected background of 1.24±0.99, and set an upper limit on the branching fraction of B(B0s→μ+μ−)<1.2×10−7 at the 95% C.L.Received 28 July 2007DOI:https://doi.org/10.1103/PhysRevD.76.092001©2007 American Physical Society