This paper reports the results of five experiments designed to investigate the effects of referential processing on sentence complexity. Gibson (Cognition, 68 (1998) 1) suggested that sentence complexity is related to the locality of integrations between dependent syntactic heads, and that an appropriate measure of locality is the number of new discourse referents intervening between the endpoints of those integrations. The experiments in this paper test, modify and extend Gibson's (1998) claims. Each experiment manipulated noun phrases (NPs) in the subject positions of object-extracted relative clauses in order to determine how different types of NPs affected sentence complexity. Experiments 1, 2 and 3 used questionnaires to gauge sentence complexity, whereas Experiments 4 and 5 used self-paced reading. The results from Experiments 1, 2, 4 and 5 suggest that the complexity of the experimental items was more closely related to the Givenness status of the embedded subject in the Givenness Hierarchy than to whether the embedded subject was old or new to the discourse. Experiment 3 compared materials in which a quantifier was rotated through subject positions of a nested relative clause structure. The results of this experiment support a discourse-processing-based distance metric for computing locality and provide evidence against a pure similarity-based account of structural complexity such as proposed by Bever (Bever, T. G. (1970). The cognitive basis of linguistic structures. In J. R. Hayes (Ed.), Cognition and the development of language (pp. 279–362). New York: Wiley).