We present a case of an 82-year-old female with subacute altered mental status, oculomotor disturbances, and ataxia. On examination, she exhibited bilateral ptosis, complete horizontal ophthalmoplegia and limited vertical eye movements during upgaze associated with prominent truncal ataxia. Cerebral MRI showed a mild hyperintensity on T2 and fluid attenuated inversion recovery sequences in the posterior brainstem extending to the upper cervical cord, without gadolinium enhancement. Clinical and radiological features suggested an encephalomyelitis with prominent brainstem involvement. We summarize the comprehensive differential diagnosis in patients with subacute brainstem encephalitis, that includes infectious, paraneoplastic syndromes and inflammatory disorders. This case highlights the relevance of performing a wide, methodical screening for malignancy in case of negative initial work-up.