Rheumatic heart disease (RHD) is one of the most common causes of cardiovascular complications in developing countries. It is a heart valve disease that typically affects children. Impaired heart valves stop functioning properly, resulting in a turbulent blood flow within the heart known as a murmur. This murmur can be detected by cardiac auscultation. However, the specificity and sensitivity of manual auscultation were reported to be low. The other alternative is echocardiography, which is costly and requires a highly qualified physician. Given the disease’s current high prevalence rate (the latest reported rate in the study area (Ethiopia) was 5.65%), there is a pressing need for early detection of the disease through mass screening programs. This paper proposes an automated RHD screening approach using machine learning that can be used by non-medically trained persons outside of a clinical setting. Heart sound data was collected from 124 persons with RHD (PwRHD) and 46 healthy controls (HC) in Ethiopia with an additional 81 HC records from an open-access dataset. Thirty-one distinct features were extracted to correctly represent RHD. A support vector machine (SVM) classifier was evaluated using two nested cross-validation approaches to quantitatively assess the generalization of the system to previously unseen subjects. For regular nested 10-fold cross-validation, an f1-score of 96.0 ± 0.9%, recall 95.8 ± 1.5%, precision 96.2 ± 0.6% and a specificity of 96.0 ± 0.6% were achieved. In the imbalanced nested cross-validation at a prevalence rate of 5%, it achieved an f1-score of 72.2 ± 0.8%, recall 92.3 ± 0.4%, precision 59.2 ± 3.6%, and a specificity of 94.8 ± 0.6%. In screening tasks where the prevalence of the disease is small, recall is more important than precision. The findings are encouraging, and the proposed screening tool can be inexpensive, easy to deploy, and has an excellent detection rate. As a result, it has the potential for mass screening and early detection of RHD in developing countries.