What is the interplay between Business Process Management (BPM) and Service-Oriented Architecture (SOA) in achieving high business process quality? In this paper, we empirically investigate the impact of both SOA and BPM on business process quality in terms of straight-through processing (STP), business-to-business integration, quality control, as well as standardization and consolidation of business processes. For the empirical evaluation of our model, we use the data of 157 German service firms. The results show that the SOA paradigm has still received rather low adoption rates in the industry. However, SOA, BPM, and related information technologies have a direct positive impact on business process quality and the analysis provides evidence for the complementarities of BPM and SOA since interaction effects between them have an additional significant impact on business process quality. Consequently, firms having adopted SOA can more effectively apply BPM.