We search for excited and exotic muon states μ∗ using an integrated luminosity of 371  pb−1 of pp collision data at s√=1.96  TeV. We search for associated production of μμ∗ followed by the decay μ∗→μγ. We compare the data to model predictions as a function of the mass of the excited muon Mμ∗, the compositeness energy scale Λ, and the gauge coupling factor f. No signal above the standard model expectation is observed. We exclude 107<853  GeV/c2 for Λ=Mμ∗ in the contact interaction model, and 100<410  GeV/c2 for f/Λ=10−2  GeV−1 in the gauge-mediated model, both at the 95% confidence level.