A 62-year-old man was admitted to our hospital because of rapidly progressive dysarthria, truncal ataxia, and gait disturbance. High titers of the ProGRP and anti-P/Q-type VGCC antibody were detected in the serum. High accumulation of [18F] was detected at the hilus of the left lung on [18F]-FDG-PET scan. A high-frequency repetitive stimulation test of the median nerve yielded an incremental response. On the basis of these findings, a diagnosis of paraneoplastic cerebellar degeneration (PCD) and Lambert-Eaton myasthenic syndrome (LEMS) associated with small cell lung carcinoma (SCLC) was diagnosed. After intravenous immunoglobulin therapy (IVIg), methylprednisolone (m-PSL) pulse therapy, and other multidisciplinary concurrent treatments, a partial regression of the SCLC and a significant improvement in neurological symptoms were observed. However, ataxia relapsed and brainstem encephalitis developed 6 months later. A marginal improvement in neurological symptoms was observed with IVIg, m-PSL pulse therapy, and intravenous cyclophosphamide pulse therapy (IVCY). SCLC also recurred later. We hypothesized that VGCC of the brainstem was damaged by anti-P/Q-type VGCC antibody.