We present a search for the flavor-changing neutral current decay Bs→μ+μ-φ in pp¯ collisions at s√=1.8 TeV, using 91 pb-1 of data collected at the Collider Detector at Fermilab (CDF). We find two candidate events for this decay, which are consistent with the background estimate of one event, and set an upper limit on the branching fraction of B(Bs→μ+μ-φ)<6.7×10-5 at a 95% confidence level. This is the first limit on the branching fraction of this decay.