Given the proximity and recent spread of rabies in Indonesia, effective rabies surveillance in dogs is a priority in Northern Australia and Papua New Guinea (PNG). Reporting of potential cases requires community engagement; therefore, the value and acceptability of such a system is critical to ensure sustainable surveillance. We used qualitative research methods to identify factors that influence the acceptability and value of community-based rabies surveillance. Thirty-two semi-structured interviews were conducted with informants in 16 communities in East Arnhem, the Northern Peninsula Area, the Torres Strait in Australia, and in Western Province, PNG. Thematic analysis identified common themes including the importance of verbal communication, particularly via radio, community meetings, and direct conversation. We also found that dogs have high value to community members through connection to culture, economic (especially hunting), and companionship. The greatest barrier to the reporting of sick dogs was insufficient veterinary services and the subsequent lack of treatment response. In some regions, acceptance that sick dogs are a normal daily occurrence and lack of trust of authorities were also barriers to reporting. The findings from this study will be used to design sustainable rabies surveillance in Northern Australia and PNG by utilizing traditional communication channels and building on existing and valued animal-management services. The methods and findings of this study complement previous quantitative research, so as to target surveillance to high-risk areas within these regions.