Using reading times and event-related brain potentials (ERPs), we investigated the processing of Japanese subject and object relative clauses (SRs/ORs). Previous research on English relative clauses shows that ORs take longer to read (King & Just, 1991) and elicit anterior negativity between fillers and gaps (King & Kutas, 1995), which is attributed to increased working memory load due to longer filler-gap distance. In contrast to English, gaps in Japanese relative clauses are less clearly marked and precede their fillers, and the linear gap-filler distance is shorter in ORs than in SRs. Nevertheless, Japanese ORs take longer to read (Ishizuka, Nakatani, & Gibson, 2003; Miyamoto & Nakamura, 2003), perhaps because in both English and Japanese, gaps in ORs are more deeply embedded, with the result that there is longer structural distance between filler and gap in their syntactic representations (O'Grady, 1997). We investigated how gap-filler association in Japanese would compare to filler-gap association in English, and whether it is linear or structural distance that determines comprehension difficulty. The results showed higher processing costs for ORs than SRs in both reading times and ERPs, and thus are most consistent with a structural distance account. The results also showed that gap-filling difficulty manifests itself as larger centro-posterior positivity in ERP responses to Japanese OR sentences, just as it does in English long-distance dependencies (cf. Kaan, Harris, Gibson, & Holcomb, 2000; Phillips, Kazanina, & Abada, 2005; Gouvea, Phillips, Kazanina, & Poeppel, 2007). There is also evidence that there is a probabilistic cue of a gap in Japanese OR sentences that triggers anterior negativity - similar to the triggering of anterior negativity by a clearly marked filler in English filler-gap sentences (cf. Kluender & Kutas, 1993a, 1993b). Thus, we argue that there is substantial similarity between the processing of English filler-gap constructions and Japanese gap-filler constructions. (Contains 1 table, 5 figures, and 6 footnotes.)