Introduction. Paraneoplastic syndromes represent rare symptom complexes resulting from the ability of tumour cells to disrupt the homeostatic processes of various bodily systems. Here we present two cases to demonstrate how such tumours may evade detection even after extensive investigation and how even relatively benign tumours can produce severe neurological symptoms. Case 1. A 69-year-old female was admitted with a subacute onset of dysarthria, ataxia, and cerebellar signs. Workup revealed a relatively benign Non-Hodgkin's Lymphoma. Case 2. A 64-year-old female was admitted with acute leg weakness, which progressed to quadriplegia and was eventually fatal over the ensuing months. Her Ca-125 was elevated, though three different CT views of her pelvis and surgical exploration failed to demonstrate any malignancy. Discussion. These cases highlight how even relatively benign or very small tumours may result in severe neurological symptoms. Suspecting and investigating paraneoplastic syndromes (PNSs) are crucial as up to 80% of patients present with PNS before there is any other indication of malignancy. A PET scan and regular surveillance may reveal occult malignancies better than CT or MRI. Neuromodulatory therapies and treatment of the underlying malignancy remain the best management options in these patients.