BACKGROUND: Voluntary assisted partner notification (aPN) services are effective in increasing access to and uptake of HIV testing among partners of people with HIV. Following recommendations by the World Health Organization in 2016, Indonesia evaluated various approaches to aPN. We present the lessons learned from formative operational research undertaken to understand provider and patient perspectives on aPN from three demonstration sites in cities with a high HIV burden. METHODS: We conducted a formative qualitative study in three cities: Jakarta, Semarang, and Denpasar between September and October 2019. We conducted six focus group discussions (FGDs) (n = 44 participants) among health-care providers, people living with HIV and the general population. We explored participant preferences and concerns about how aPN should be delivered, including the methods of and messaging for contacting partners. All FGDs were conducted in the Indonesian language. Qualitative data were analysed using thematic analysis. RESULTS: aPN was acceptable across different participant populations, although with caveats. Some differences were observed between the general population, providers and people living with HIV. People living with HIV were mainly concerned with confidentiality of the procedure and preferred the use of telecommunication and messages that avoid explicit mention of HIV exposure. Providers preferred similar approaches but for different reasons, being concerned mainly with self-efficacy and security. There was consensus regarding dual referral models. The use of phone calls and short messages were preferred as these are perceived to minimize negative reactions and stigma, protect client confidentiality and are suitable in the current legal situation. The general population was mainly concerned with effectiveness and prefer direct provider-led approaches, such as preferring in-person meeting with explicit notification of potential HIV exposure. CONCLUSIONS: We found consensus among stakeholders on acceptance of aPN, especially dual referral methods. Development and implementation of aPN protocols should also consider clients' individual situations and concerns regarding safeguarding of confidentiality, and offer a range of options to accommodate all stakeholders involved.