Background: Colic is a common condition in infants <4 months of age. Attempts to treat infantile colic with probiotics have shown variable efficacy and overall low evidence of success. In this work, we tested the hypothesis that oral administration of Bifidobacterium longum CECT7894 (KABP042) and Pediococcus pentosaceus CECT8330 (KABP041) mix (1 × 109 colony forming units) would improve the symptoms of infantile colic. Methods: A total of 112 exclusively breastfed or mixed fed infants aged <2 months and meeting the ROME IV criteria for infantile colic were recruited. The infants were randomized in a double-blind, placebo-controlled trial to receive orally administered probiotics (intervention group, IG, n = 48) or placebo (placebo group, PG, n = 42) daily for 21 days. Results: Infants in the IG had significantly shorter crying time (p < 0.001) on day 7 [IG vs. PG, median (25-75th percentile): 38 (3.5-40.5) vs. 62 (40-108) min/day], day 14 [IG vs. PG: 20 (0-40) vs. 50 (30-75) min/day], and day 21 [IG vs. PG: 14 (0-33) vs. 40 (28-62) min/day]. Higher responder ratio and fewer crying/fussing episodes on days 7, 14, and 21 and better stool consistency on day 21 were observed in the IG (p < 0.01) as compared to the PG. Conversely, no significant effects on stool frequency or quality of life were observed. Conclusions: In summary, daily oral administration of B. longum CECT7894 (KABP042) and P. pentosaceus CECT8330 (KABP041) was an effective treatment for shortening crying time due to infantile colic and for improving fecal consistency. This trial was registered retrospectively in December 2019 with a trial number of ISRCTN92431452.