Plants have developed complex defense mechanisms to protect themselves against pathogens. A wide-host-range fungus, Austropuccinia psidii, which has caused severe damage to ecosystems and plantations worldwide, is a major threat to Australian ecosystems dominated by members of the family Myrtaceae. In particular, the east coast wetland foundation tree species Melaleuca quinquenervia, appears to be variably susceptible to this pathogen. Understanding the molecular basis of host resistance would enable better management of this rust disease. We identified resistant and susceptible individuals of M. quinquenervia and explored their differential gene expression in order to discover the molecular basis of resistance against A. psidii. Rust screening of germplasm showed a varying degree of response, with fully resistant to highly susceptible individuals. We used transcriptome profiling in samples collected before and at 5 days postinoculation (dpi). Differential gene expression analysis showed that numerous defense-related genes were induced in susceptible plants at 5 dpi. Mapping reads against the A. psidii genome showed that only susceptible plants contained fungal-derived transcripts. Resistant plants exhibited an overexpression of candidate A. psidii resistance-related genes such as receptor-like kinases, nucleotide-binding site leucine-rich repeat proteins, glutathione S-transferases, WRKY transcriptional regulators, and pathogenesis-related proteins. We identified large differences in the expression of defense-related genes among resistant individuals.