Background: The HealthMap project is developing an intervention to reduce cardiovascular risk in people living with HIV. As part of the formative stages of the intervention design, we sought to understand the needs of people with HIV (PWHIV). Methods: Two concept-mapping workshops with PWHIV (n = 10), and one with HIV care providers (n = 6) were conducted. The workshop findings were consolidated into a questionnaire administered to PWHIV (n = 300) and HIV care providers (n = 107). Participants were asked to rate the importance of each of 81 presented needs and the degree to which it was currently being met. Results: Workshops provided insights into what PWHIV perceive they need, to live with and manage their condition, and its impact on their life; these included: (1) clinical science research and development; (2) information and support; (3) personal situation; (4) healthcare quality; (5) access to services; (6) access to services specific to ageing; and (7) social justice. Questionnaire results revealed that PWHIV considered information and support, and research and development most important. For providers, healthcare quality, clients’ personal situation, and social justice were most important. In terms of unmet needs, PWHIV and providers both highlighted issues in the areas of social justice, and access to aged care services. Conclusions: PWHIV and HIV providers continue to report unmet needs in the areas of social justice and emerging concerns about access to aged care services. Services must continue to address these issues of access and equity.