The Papua New Guinea (PNG) Department of Health introduced a 'test and treat' malaria case management protocol in 2011. This study assesses health worker compliance with the test and treat protocol on a wide range of measures, examines self-reported barriers to health worker compliance as well as health worker attitudes towards the test and treat protocol. Data were collected by cross-sectional survey conducted in randomly selected primary health care facilities in 2012 and repeated in 2014. The combined survey data included passive observation of current or recently febrile patients (N = 771) and interviewer administered questionnaires completed with health workers (N = 265). Across the two surveys, 77.6% of patients were tested for malaria infection by rapid diagnostic test (RDT) or microscopy, 65.6% of confirmed malaria cases were prescribed the correct antimalarials and 15.3% of febrile patients who tested negative for malaria infection were incorrectly prescribed an antimalarial. Overall compliance with a strictly defined test and treat protocol was 62.8%. A reluctance to test current/recently febrile patients for malaria infection by RDT or microscopy in the absence of acute malaria symptoms, reserving recommended antimalarials for confirmed malaria cases only and choosing to clinically diagnose a malaria infection, despite a negative RDT result were the most frequently reported barriers to protocol compliance. Attitudinal support for the test and treat protocol, as assessed by a nine-item measure, improved across time. In conclusion, health worker compliance with the full test and treat malaria protocol requires improvement in PNG and additional health worker support will likely be required to achieve this. The broader evidence base would suggest any such support should be delivered over a longer period of time, be multi-dimensional and multi-modal.