Anti-Hu encephalomyelitis is one of the most frequent paraneoplastic syndromes, classically presenting with diffuse neurological involvement. We report a 69-year-old man presenting with a three-month isolated, progressive gait disorder with normal neurological examination, except for loss of balance and gait failure reminding frontal disequilibrium, only accompanied by a very mild rigidity of his right foot. MRI of the brain showed hyperintensities in both amygdale and left putamen. EMG study showed no abnormal continuous spontaneous fiber activity. Because of fast progression and MRI findings, anti-Hu antibodies were tested, resulting positive. Mediastinal biopsy of two adenopathies detected by body-PET, confirmed an oat-cell carcinoma. The patient received oral steroids and oncological therapy. One year later, the tumor is in remission. His gait and abnormal posture of right leg are normal. Only mild residual hyperintensities persist on follow-up MRI. A paraneoplastic syndrome should be considered in the differential diagnosis of subacute, fast progressive gait disorders.