This chapter talks about a 75-year-old retired sailor who was in very good overall physical condition. At the first assessment, the sailor reported a gradual cognitive decline, subjectively described as memory impairment, during the last 2 years. The neurologist diagnosed mild right-sided Parkinsonism in upper body, with tremor and bradykinesia, but no rigor. Walking was near normal, but he was unsteady on turning and had a pathological pull-test. This case presented with asymmetric Parkinsonism, and cognitive impairment was noted at the time of diagnosis. Thus, the important differential diagnoses were possible: dementia associated with Lewy Bodies (DLB) or Dementia associated with Parkinson's disease (PDD). DLB is characterized by dementia accompanied by idiopathic Parkinsonism, cognitive fluctuation, and persistent visual hallucinations. PDD and DLB have similar clinical presentation as well as underlying brain changes, and differentiation between the two syndromes is entirely based on the relative timing of Parkinsonism and cognitive impairment.