This chapter presents a survey of medical data mining focusing upon the use of heuristic techniques. We observe that medical mining has some unique ethical issues because of the human arena in which the conclusions are outworked. The chapter proposes a forward looking responsibility for mining practitioners that includes evaluating and justifying data mining methods–a task especially salient when heuristic methods are used. We define heuristics broadly to include those methods that are applicable for large volumes of data, as well as those specifically directed to dealing with uncertainty, and those concentrated upon efficiency. We specifically consider characteristics of medical data, reviewing a range of mining applications and approaches. We conclude with some suggestions directed towards establishing a set of guidelines for heuristic methods in medicine.