A search for excited leptons is carried out with the CMS detector at the LHC, using 36 inverse picobarns of pp collision data recorded at sqrt(s) = 7 TeV. The search is performed for associated production of a lepton and an oppositely charged excited lepton pp to l l*, followed by the decay l* to l gamma, resulting in the l l gamma final state, where l = electron or muon. No excess of events above the standard model expectation is observed. Interpreting the findings in the context of l* production through four-fermion contact interactions and subsequent decay via electroweak processes, first upper limits are reported for l* production at this collision energy. The exclusion region in the compositeness scale Lambda and excited lepton mass M(l*) parameter space is extended beyond previously established limits. For Lambda = M(l*), excited lepton masses are excluded below 1070 GeV/c^2 for e* and 1090 GeV/c^2 for mu* at the 95% confidence level.