Anew search signature for excited leptons is explored. Excited muons are sought in the channel pp -> mu mu* -> mu mu jet jet, assuming both the production and decay occur via a contact interaction. The analysis is based on 20.3 fb(-1) of pp collision data at a centre-of-mass energy of root s = 8 TeV taken with the ATLAS detector at the large hadron collider. No evidence of excited muons is found, and limits are set at the 95% confidence level on the cross section times branching ratio as a function of the excited-muon mass m(mu)*. For m(mu)* between 1.3 and 3.0 TeV, the upper limit on sigma B(mu* -> mu q (q) over bar) is between 0.6 and 1 fb. Limits on sB are converted to lower bounds on the compositeness scale Lambda. In the limiting case Lambda = m(mu)*, excited muons with a mass below 2.8 TeV are excluded. With the same model assumptions, these limits at larger mu* masses improve upon previous limits from traditional searches based on the gauge-mediated decay mu* -> mu gamma.