Background: The relationship between objective measurements and subjective symptoms of patients with spinal stenosis and the degree of narrowing of the spinal canal is not clear. The purpose of this study was to evaluate patients undergoing surgery for lumbar spinal stenosis and intermittent neurogenic claudication with functional testing, quantitative imaging, and patient self-assessment. Methods: Sixty-two patients with lumbar spinal stenosis and neurogenic claudication were prospectively enrolled in the study. All underwent preoperative magnetic resonance imaging and/or computed tomography myelography, and all were treated with decompressive surgery and were followed for a minimum of two years. The evaluation included treadmill and bicycle exercise tests as well as patient self-assessment with use of the Oswestry Disability Index and a visual analog pain scale preoperatively and postoperatively. Results: Preoperatively fifty-eight (94%) of the patients had a positive result (provocation of symptoms) on the treadmill test and twenty-seven (44%) had a positive result on the bicycle test, whereas postoperatively six and twelve, respectively, had positive results. The mean preoperative scores on the Oswestry Disability Index and visual analog pain scale were 58.4 and 7.1, respectively. Postoperatively, these scores decreased to 21.1 and 2.3, respectively, and both decreases were significant (p < 0.05). Forty-seven (76%) of the patients were seen to have central stenosis on the preoperative imaging studies; forty-one of them had a cross-sectional area of the dural tube of <100 mm2 at at least one level and twelve had a cross-sectional area of <100 mm2 at at least two levels. Conclusions: A positive treadmill test was consistent with a diagnosis of spinal stenosis and neurogenic claudication in >90% of the patients preoperatively. Following surgical decompression of the lumbar spinal stenosis, more functional improvement was demonstrated by the treadmill test than by the bicycle test. The scores on the Oswestry Disability Index and visual analog pain scale also improved postoperatively. The severity of central canal narrowing at a single level does not appear to limit the postoperative improvement in either functional ability or patient self-assessment. Patients with multilevel central stenosis were, on the average, older and walked a shorter distance preoperatively and postoperatively, although the improvement in their postoperative self-assessment scores was similar to that of patients with single-level stenosis.