Digital clinical decision support tools have contributed to improved quality of care at primary care level health facilities. However, data from real-world randomized trials are lacking. We conducted a cluster randomized, open-label trial in Tanzania evaluating the use of a digital clinical decision support algorithm (CDSA), enhanced by point-of-care tests, training and mentorship, compared with usual care, among sick children 2 to 59 months old presenting to primary care facilities for an acute illness in Tanzania (ClinicalTrials.gov NCT05144763). The primary outcome was the mean proportion of 14 major Integrated Management of Childhood Illness (IMCI) symptoms and signs assessed by clinicians. Secondary outcomes included antibiotic prescription, counseling provided, and the appropriateness of antimalarial and antibiotic prescriptions. A total of 450 consultations were observed in 9 intervention and 9 control health facilities. The mean proportion of major symptoms and signs assessed in intervention health facilities was 46.4% (range 7.7% to 91.7%) compared to 26.3% (range 0% to 66.7%) in control health facilities, an adjusted difference of 15.1% (95% confidence interval [CI] 4.8% to 25.4%). Only weight, height, and pallor were assessed statistically more often when using the digital CDSA compared to controls. Observed antibiotic prescription was 37.3% in intervention facilities, and 76.4% in control facilities (adjusted risk ratio 0.5; 95% CI 0.4 to 0.7; p<0.001). Appropriate antibiotic prescription was 81.9% in intervention facilities and 51.4% in control facilities (adjusted risk ratio 1.5; 95% CI 1.2 to 1.8; p = 0.003). The implementation of a digital CDSA improved the mean proportion of IMCI symptoms and signs assessed in consultations with sick children, however most symptoms and signs were assessed infrequently. Nonetheless, antibiotics were prescribed less often, and more appropriately. Innovative approaches to overcome barriers related to clinicians' motivation and work environment are needed.