BACKGROUND: Corruption is widespread in Nigeria's health sector but the reasons why it exists and persists are poorly understood and it is often seen as intractable. We describe a consensus building exercise in which we asked health workers and policy-makers to identify and prioritise feasible responses to corruption in the Nigerian health sector. METHODS: We employed three sequential activities. First, a narrative literature review identified which types of corruption are reported in the Nigerian health system. Second, we asked 21 frontline health workers to add to what was found in the review (based on their own experiences) and prioritise them, based on their significance and the feasibility of assessing them, by means of a consensus building exercise using a Nominal Group Technique (NGT). Third, we presented their assessments in a meeting of 25 policy-makers to offer their views on the practicality of implementing appropriate measures. RESULTS: Participants identified 49 corrupt practices from the literature review and their own experience as most important in the Nigerian health system. The NGT prioritised: absenteeism, procurement-related corruption, under-the-counter payments, health financing-related corruption, and employment-related corruption. This largely reflected findings from the literature review, except for the greater emphasis on employment-related corruption from the NGT. Absenteeism, Informal payments and employment-related corruption were seen as most feasible to tackle. Frontline workers and policy-makers agreed that tackling corrupt practices requires a range of approaches. CONCLUSION: Corruption is recognized in Nigeria as widespread but often seems insurmountable. We show how a structured approach can achieve consensus among multiple stakeholders, a crucial first step in mobilizing action to address corruption.