Self-organized activation patterns in excitable media such as spiral waves and spatio-temporal chaos underlie dangerous cardiac arrhythmias. While the interaction of single spiral waves with different types of heterogeneity has been studied extensively, the effect of heterogeneity on fully developed spatio-temporal chaos remains poorly understood. We investigate how the complexity and stability properties of spatio-temporal chaos in the Bar-Eiswirth model of excitable media depend on the heterogeneity of the underlying medium. We employ different measures characterizing the chaoticity of the system and find that the spatial arrangement of multiple discrete lower excitability regions has a strong impact on the complexity of the dynamics. Varying the number, shape, and spatial arrangement of the heterogeneities, we observe strong emergent effects ranging from increases in chaoticity to the complete cessation of chaos, contrasting the expectation from the homogeneous behavior. The implications of our findings for the development and treatment of arrhythmias in the heterogeneous cardiac muscle are discussed.