Critical Congenital Heart Disease (CCHD) screening that only uses oxygen saturation (SpO2), measured by pulse oximetry, fails to detect an estimated 900 US newborns annually. The addition of other pulse oximetry features such as perfusion index (PIx), heart rate, pulse delay and photoplethysmography characteristics may improve detection of CCHD, especially those with systemic blood flow obstruction such as Coarctation of the Aorta (CoA). To comprehensively study the most relevant features associated with CCHD, we investigated interpretable machine learning (ML) algorithms by using Recursive Feature Elimination (RFE) to identify an optimal subset of features. We then incorporated the trained ML models into the current SpO2-alone screening algorithm. Our proposed enhanced CCHD screening system, which adds the ML model, improved sensitivity by approximately 10 percentage points compared to the current standard SpO2-alone method with minimal to no impact on specificity.Clinical relevance- This establishes proof of concept for a ML algorithm that combines pulse oximetry features to improve detection of CCHD with little impact on false positive rate.