OBJECTIVES: The cost-effectiveness of diagnosis raises challenges in identifying the possible ways to combine tests, obtaining long-term outcomes and costs, and understanding uncertainty. We report our approach to these issues in the context of the cost-effectiveness of prostate cancer diagnosis. METHODS: Our objective was to identify the cost-effective way of using biopsy and imaging scans to diagnose prostate cancer based on the PROMIS study. We built a decision tree to determine the sensitivity of 32 test sequences with multiple cut-offs, forming 383 strategies. We developed a Markov model to calculate the long-term outcomes and costs with and without treatment. To obtain transition probabilities, we developed a calibration model, parameterised with aggregated data and digitised survival curves. RESULTS: The decision tree identified 14 strategies on the cost-sensitivity frontier; those that are expected to detect the most cancers per pound spent. Considering uncertainty, an additional 36 strategies presented with some likelihood of forming the sensitivity frontier. We found that radical treatment was highly cost-effective compared to watchful waiting (ICER~£3,000/QALY), leaving scope for investment in intensive diagnostic strategies. We identified the cost-effective strategy by assigning the pay-offs of treatment to the decision tree, and found that the cost-effective strategy for the UK context detected 95% of cancers (ICER=£7,076/QALY). Less costly and less sensitive strategies would become cost-effective if treatment was proven to be less cost-effective or if there were multiple test-and-treat opportunities over time. CONCLUSIONS: Cost-effectiveness analysis of diagnosis can easily expand into large numbers of strategies. A large proportion can be removed if their probability of forming the cost-sensitivity frontier is zero and have the same direct impact on health. Calibration models can provide an approximation to transition probabilities, but uncertainties remain on the impact of multiple test-and-treat opportunities. Communicating cost-effectiveness results and uncertainty for a large number of strategies requires novel graphical representations.