Abstract Background Malaria places a significant burden on the limited resources of many low income countries. Knowing more about why and where people seek treatment will enable policy makers to better allocate the limited resources. This study aims to better understand what influences treatment-seeking behaviour for malaria in one such low-income country context, Papua New Guinea (PNG). Methods Two culturally, linguistically and demographically different regions in PNG were selected as study sites. A cross sectional household survey was undertaken in both sites resulting in the collection of data on 928 individuals who reported suffering from malaria in the previous four weeks. A probit model was then used to identify the factors determining whether or not people sought treatment for presumptive malaria. Multinomial logit models also assisted in identifying the factors that determined where people sought treatments. Results Results in this study build upon findings from other studies. For example, while distance in PNG has previously been seen as the primary factor in influencing whether any sort of treatment will be sought, in this study cultural influences and whether it was the first, second or even third treatment for a particular episode of malaria were also important. In addition, although formal health care facilities were the most popular treatment sources, it was also found that traditional healers were a common choice. In turn, the reasons why participants chose a particular type of treatment differed according to the whether they were seeking an initial or subsequent treatments. Conclusions Simply bringing health services closer to where people live may not always result in a greater use of formal health care facilities. Policy makers in PNG need to consider within-country variation in treatment-seeking behaviour, the important role of traditional healers and also ensure that the community fully understands the potential implications of not seeking treatment for illnesses such as malaria at a formal health care facility.