Abstract: In recent days, the data mining techniques are fascinatingly applied in healthcare domain. It proved that these techniques are suitable to extract knowledge from medical domain. Association Rule Mining (ARM) is mined valuable information from large voluminous databases. But most of ARM algorithms are mined many uninteresting or unrelated knowledge. We proposed new n-cross validation based Apriori (nVApriori) algorithm to mine domain irrelevant rules. Acquired Immuno Deficiency Syndrome (AIDS) is a challenge infection in the field of medical domain. This work proposes a new dataset for AIDS/HIV infected patients’ case history. The data were collected from Midwest clinics, London. The nVApriori algorithm applies with the proposed dataset. It mines many interesting rules, provides much useful information to domain experts. The proposed algorithm is performed better than traditional Apriori, most interesting rule mining algorithm, Non redundant rule mining algorithm.