We report on a search for the flavor-changing neutral current decay D0→μ+μ- in pp¯ collisions at s√=1.96TeV using 65pb-1 of data collected by the CDF II experiment at the Fermilab Tevatron Collider. A displaced-track trigger selects long-lived D0 candidates in the D0→μ+μ- search channel, the kinematically similar D0→π+π- channel used for normalization, the Cabibbo-favored D0→K-π+ channel used to optimize the selection criteria in an unbiased manner, and their charge conjugates. Finding no signal events in the D0→μ+μ- search window, we set an upper limit on the branching fraction B(D0→μ+μ-)<~2.5×10-6 (3.3×10-6) at the 90% (95%) confidence level.