Updated publication reference for PubMed record(s): 30259100. Due to the high capacity of their secretion machinery Gram-positive bacteria from the genus Bacillus are important expression hosts for the high-yield production of enzymes in industrial biotechnology. However, to date strains from only a few Bacillus species are used for enzyme production at the industrial scale. In this work, we introduce with Paenibacillus polymyxa DSM 292 a member of a different genus as a novel host for secretory protein production. The model gene cel8A from Clostridium thermocellum was chosen as an easily detectable reporter gene with industrial relevance to demonstrate efficient heterologous expression and secretion in P. polymyxa. The yield of the secreted cellulase Cel8A was increased by optimizing the expression medium and testing various promoter sequences on the expression plasmid pBACOV. To identify promising new promoter sequences from the genome of P. polymyxa itself, quantitative mass spectrometry was used to analyze the secretome. The most strongly secreted host proteins were identified and the promoters regulating the expression of the corresponding genes were selected. Eleven promoter sequences were cloned and tested, including well-characterized promoters from B. subtilis and B. megaterium. The best result was achieved with the promoter of the hypothetical protein PPOLYM_03468 from P. polymyxa, which in combination with the improved expression medium enabled the production of 5,475 U/l Cel8A which represents a 6.2-fold increase compared to the reference promoter PaprE. The set of promoters described in this work covers a broad range of promoter strengths useful for heterologous expression in the new host P. polymyxa.