Polymorphism is a well-known but important phenomenon in the field of solid-state chemistry. Crystalline materials can form various polymorphs and present drastically varied physical and chemical properties. Herein, systematic exploration of the BaO-MoO3 binary system leads to the discovery of a new barium molybdate, α-BaMo3O10. The temperature-dependent phase transition from α-BaMo3O10 to β-BaMo3O10 is confirmed. The tunable linear and nonlinear optical properties induced by the phase transition are confirmed by both experimental and theoretical approaches. Also, β-BaMo3O10 is identified as a nonlinear-optical crystal for the first time. The origin of linear- and nonlinear-optical properties of BaMo3O10 polymorphs is confirmed by the additional theoretical means. This work indicates that a small change in the structure can induce tunable symmetries and thereby widely divergent optical properties.