Rheumatic heart disease (RHD) remains a disease of international importance, yet little has been published about disease progression in a contemporary patient cohort. Multi-state models provide a well-established method of estimating rates of transition between disease states, and can be used to evaluate the cost-effectiveness of potential interventions. We aimed to create a multi-state model for RHD progression using serial clinical data from a cohort of Australian patients. The Northern Territory RHD register was used to identify all Indigenous residents diagnosed with RHD between the ages of 5 and 24 years in the time period 1999-2012. Disease severity over time, surgeries, and deaths were evaluated for 591 patients. Of 96 (16.2%) patients with severe RHD at diagnosis, 50% had proceeded to valve surgery by 2 years, and 10% were dead within 6 years. Of those diagnosed with moderate RHD, there was a similar chance of disease regression or progression over time. Patients with mild RHD at diagnosis were the most stable, with 64% remaining mild after 10 years; however, 11.4% progressed to severe RHD and half of these required surgery. The prognosis of young Indigenous Australians diagnosed with severe RHD is bleak; interventions must focus on earlier detection and treatment if the observed natural history is to be improved. This multi-state model can be used to predict the effect of different interventions on disease progression and the associated costs.