Aim To investigate the effect of influenza vaccination with or without probiotic supplementation on the immune response and incidence of influenza-like illness (ILI) in the elderly. Methods A randomized double-blind, placebo-controlled trial with a modified factorial design was conducted in 554 healthy elderly subjects aged 67 ± 5.6 (ranging from 60–90) years old in the Primary Health Care Center (Puskesmas area) of the Pulo Gadung District East Jakarta. Subjects received either a trivalent influenza vaccine or placebo at the start of the study, and a probiotic supplement (Lactobacillus helveticus R0052 and Lactobacillus rhamnosus R0011) or a placebo for 6 months. Subjects were randomly assigned into four intervention groups: influenza vaccine and probiotics (n = 141), influenza vaccine and placebo (n = 136), placebo and probiotics (n = 140), and both placebo (n = 137). The primary outcome was ILI incidence within 6 months. The secondary outcomes were seroprotection and seroconversion rates at 1, 4, and 6 months after administering the interventions. Results This study showed that the trivalent influenza vaccine increased seroprotection (RR 3.6 [95%CI 2.92–4.47]; p<0.010) and seroconversion (RR 29.8 [95%CI 11.1–79.5]; p<0.010) rates 1 month after vaccination in elderly people while the probiotic supplement did not alter influenza antibody titers (p = 1.000 and p = 0.210). The relative ILI incidence risk was similar between vaccinated and non-vaccinated groups, as well as in the probiotic group compared to the non-probiotic group. Conclusion The tested trivalent influenza vaccine significantly induced seroprotection and seroconversion in the vaccinated subjects, while probiotics administration did not influence these parameters. Vaccinated individuals displayed a similarly low ILI incidence as those in the Control Group. However, the observed trend towards a reduction of ILI incidence with probiotics supplementation warrants further assessments in a larger, at-risk population.