Full notification of deaths and compilation of good quality cause of death data are core, sequential and essential components of a functional civil registration and vital statistics (CRVS) system. In collaboration with the Government of Papua New Guinea (PNG), trial mortality surveillance activities were established at sites in Alotau District in Milne Bay Province, Tambul-Nebilyer District in Western Highlands Province and Talasea District in West New Britain Province.Provincial Health Authorities trialled strategies to improve completeness of death notification and implement an automated verbal autopsy methodology, including use of different notification agents and paper or mobile phone methods. Completeness of death notification improved from virtually 0% to 20% in Talasea, 25% and 75% using mobile phone and paper notification strategies, respectively, in Alotau, and 69% in Tambul-Nebilyer. We discuss the challenges and lessons learnt with implementing these activities in PNG, including logistical considerations and incentives.Our experience indicates that strategies to maximise completeness of notification should be tailored to the local context, which in PNG includes significant geographical, cultural and political diversity. We report that health workers have great potential to improve the CRVS programme in PNG through managing the collection of notification and verbal autopsy data. In light of our findings, and in consultation with the main government CRVS stakeholders and the National CRVS Committee, we make recommendations regarding the requirements at each level of the health system to optimise mortality surveillance in order to generate the essential health intelligence required for policy and planning.