Progressive multifocal leukoencephalopathy (PML) is a feared entity that occurs most frequently in conditions of extreme immunodeficiency. The diagnosis is often made long after the onset of symptoms due to the physicians' unfamiliarity, and the unavailability of diagnostic tests in some medical centers. Although the incidence of PML is decreasing among HIV patients with the advent of highly active antiretroviral therapy (HAART), in Brazil this entity is the fourth highest neurological complication among these patients. The authors present the case of a middle-aged man who tested positive for HIV concomitantly with the presentation of hyposensitivity in the face and the right side of the body, accompanied by mild weakness in the left upper limb. The clinical features worsened rapidly within a couple of weeks. The diagnostic work-up pointed to the working diagnosis of PML after brain magnetic resonance imaging; however, the detection of the John Cunningham virus (JCV) in the cerebral spinal fluid was negative. HAART was started but the patient died after 7 weeks of hospitalization. The autopsy revealed extensive multifocal patchy areas of demyelination in the white matter where the microscopy depicted demyelination, oligodendrocytes alterations, bizarre atypical astrocytes, and perivascular lymphocytic infiltration. The immunohistochemistry was positive for anti-SV40, and the polymerase chain reaction of the brain paraffin-embedded tissue was positive for JCV. The authors highlight the challenges for diagnosing PML, as well as the devastating outcome of PML among HIV patients.