The iron-based compound BaFe2S3 has received considerable attention in recent years due to its unique electronic properties with important applications. But, there has been relatively little attention devoted to the structure evolution of BaFe2S3 under high pressure. Here, we report a detailed theoretical study of the structural, electronic and sound velocity properties of BaFe2S3 under high pressure by CALYPSO structure search method in combination with the first-principles calculations. We have uncovered three novel structures of BaFe2S3 under high pressure with space group P2221, Imm2, and C2/m symmetries. Theoretical calculations reveal that the structures of BaFe2S3 under high pressure satisfy the phase transition sequence of Cmcm → P2221 → Imm2 → C2/m, and the corresponding transition pressures are 31.6, 47.4 and 57.0 GPa, respectively. Our results enrich the high pressure phases of BaFe2S3 and will stimulate future experiments to synthesize these new phases.