Marijuana (MJ) use and HIV infection are both associated with neurocognitive deficits, yet there is little research to date examining their interactions, specifically how they pertain to procedural learning (PL). We examined a sample of 86 individuals with a history of dependence for multiple substances who underwent a comprehensive evaluation including measures of mental health, substance use history, and three measures of PL: the photoelectric Rotary Pursuit Task (RPT), the Star Mirror Tracing Task (SMT), and the Weather Prediction Task (WPT). We found that a positive HIV serostatus and a history of marijuana dependence were both independently associated with overall poorer performance on the SMT and RPT in this sample of individuals with a history of dependence for multiple substances. Rate of improvement across trial blocks did not differ as a function of HIV serostatus or history of marijuana dependence. Although we found no significant HIV × MJ interaction for any of the PL tasks, we did observe evidence of additive negative effects from HIV and a history of marijuana dependence on overall performance on the SMT and RPT, but not the WPT. The findings suggest that complex motor skills are adversely affected among abstinent polysubstance users with a history of marijuana dependence and that such deficits are compounded by HIV.