Summary: Querying inconsistent knowledge bases is an intriguing problem that gave rise to a flourishing research activity in the knowledge representation and reasoning community during the last years. It has been extensively studied in the context of description logics (DLs), and its computational complexity is rather well-understood. Although DLs are popular formalisms for modeling ontologies, it is generally agreed that rule-based ontologies are well-suited for data-intensive applications, since they allow us to conveniently deal with higher-arity relations, which naturally occur in standard relational databases. The goal of this work is to perform an in-depth complexity analysis of querying inconsistent knowledge bases in the case of the main decidable classes of existential rules, based on the notions of guardedness, linearity, acyclicity, and stickiness, enriched with negative (a.k.a. denial) constraints. Our investigation concentrates on three central inconsistency-tolerant semantics: the ABox repair (AR) semantics, considered as the standard one, and its main sound approximations, the intersection of repairs (IAR) semantics and the intersection of closed repairs (ICR) semantics.