HIV-associated vacuolar myelopathy (HIV-VM) is the most common cause of spinal disease in HIV/AIDS. HIV-VM causes progressive spastic paraparesis, sensory ataxia, and autonomic dysfunction. It is a progressive myelopathy that shares features with subacute combined degeneration seen in vitamin B12 deficiency as well as other neurological diseases and can occur synchronously with HIV-associated dementia (HAD). Here, we describe a rare case in which a patient's initial presentation of HIV/AIDS was both HIV-VM and HAD. A fifty-three-year-old man presented with a six-month history of numerous falls due to progressive gait instability with associated memory loss, tremor, urinary retention, and impotence. His exam was significant for hyperreflexia and weakness in bilateral lower extremities, upgoing plantar reflex, dysmetria, and ataxic gait. MRI-brain was notable for nonspecific volume loss and diffusely increased T2 signal throughout the supratentorial white matter. Lumbar puncture showed isolated lymphocytic pleocytosis with all other CSF testing unremarkable. He ultimately tested positive for HIV-1, with a CD4 count of 157 cells/mm3 and a viral load of 874,000 copies/mL. He was diagnosed with HIV-VM and HAD which improved after several months of antiretroviral therapy. This case highlights the importance of considering HIV testing in a patient with a sensory neuropathy and/or progressive cognitive impairment.