The integration, mining, and analysis of person-specific data can provide enormous opportunities for organiza-tions, governments, and researchers to leverage today’s massive data collections. However, the use of personal or otherwise sen-sitive data also raises concerns about the privacy, confidentiality, and potential discrimination of people. Privacy-preserving record linkage (PPRL) is a growing research area that aims at inte-grating sensitive information from multiple disparate databases held by different organizations while preserving the privacy of the individuals in these databases by not revealing their iden-tities and thereby preventing discrimination. PPRL approaches are increasingly required in many real-world application areas ranging from healthcare to national security. Previous approaches to PPRL have mostly focused on linking only two databases. Scaling PPRL to several databases is an open challenge since privacy threats as well as the computation and communication costs increase significantly with the number of databases involved. We thus propose a new encoding method of sensitive data based on Counting Bloom Filters (CBF) to improve privacy for multi-party PPRL (MP-PPRL). We investigate optimizations to reduce computation and communication costs for CBF-based MP-PPRL. Our empirical evaluation with real datasets demonstrates the viability of our approach in terms of scalability, linkage quality, and privacy.