Whether logical inference is available without language is highly debated. One such inference is the disjunctive syllogism (A Or B, Not A, Therefore B). Evidence from non-linguistic search tasks suggests that that the syllogism may be unavailable before age 3 (Mody & Carey, 2016). However, in a replication of the same task using language (i.e., verbal negation), even 2.5-year-olds succeeded (Grigoroglou, et al., 2019). Here we explore the role of language in children's logical reasoning. 2.5-, 3- and 4-year-olds performed a non-linguistic search task, after a short training in reasoning by exclusion. Half of the children received linguistic training (e.g., heard “there is no coin in X cup”); half received non-linguistic training (i.e., saw that one location was empty). Results show that 2.5-year-olds who received linguistic training succeeded in disjunctive syllogism but those who received non-linguistic training failed. We conclude that the presence of verbal negation facilitated logical reasoning.