Background Despite cognitive deficits frequently represent the first clinical manifestations of Progressive Multifocal Leukoencephalopathy (PML) in Natalizumab-treated MS patients, the importance of cognitive deficits in PML diagnosis is still under-investigated. The aim of the current study is to investigate the cognitive deficits at PML diagnosis in a group of Italian patients with PML. Methods Thirty-four PML patients were included in the study. The demographic and clinical data, the lesion load and localization, and the longitudinal clinical course was compared between patients with (n = 13) and without (n = 15) cognitive deficit upon PML suspicion (the remaining six patients were asymptomatic). Clinical presentation of cognitive symptoms was described in detail. Result After symptoms detection, the time to diagnosis resulted to be shorter for patients presenting with cognitive than for patients with non cognitive onset (p = 0.03). Within patients with cognitive onset, six patients were presenting with language and/or reading difficulties (46.15%); five patients with memory difficulties (38.4%); three patients with apraxia (23.1%); two patients with disorientation (15.3%); two patients with neglect (15.3%); one patients with object agnosia (7.7%), one patient with perseveration (7.7%) and one patient with dementia (7.7%). Frontal lesions were less frequent (p = 0.03), whereas temporal lesions were slightly more frequent (p = 0.06) in patients with cognitive deficits. The longitudinal PML course seemed to be more severe in cognitive than in non cognitive patients (F = 2.73, p = 0.03), but differences disappeared (F = 1.24, p = 0.29) when balancing for the incidence of immune reconstitution syndrome and for other treatments for PML (steroids, plasma exchange (PLEX) and other therapies (Mefloquine, Mirtazapine, Maraviroc). Conclusion Cognitive deficits at PML onset manifest with symptoms which are absolutely rare in MS. Their appearance in MS patients should strongly suggest PML. Clinicians should be sensitive to the importance of formal neuropsychological evaluation, with particular focus on executive function, which are not easily detected without a formal assessment.