The assembly of core histones onto eukaryotic DNA is modulated by several histone chaperone complexes, including Asf1, CAF-1 and HIRA. Asf1 is a unique histone chaperone that participates in both the replication-dependent and replication-independent pathways. Here we report the crystal structures of the apo-form of fission yeast Asf1/Cia1 (SpAsf1N; residues 1-161) as well as its complexes with the B domain of the fission yeast HIRA orthologue Hip1 (Hip1B) and the C-terminal region of the Cac2 subunit of CAF-1 (Cac2C). The mode of the fission yeast Asf1N-Hip1B recognition is similar to that of the human Asf1-HIRA recognition, suggesting that Asf1N recognition of Hip1B/HIRA is conserved from yeast to mammals. Interestingly, Hip1B and Cac2C show remarkably similar interaction modes with Asf1. The binding between Asf1N and Hip1B was almost completely abolished by the D37A and L60A/V62A mutations in Asf1N, indicating the critical role of salt-bridge and van der Waals contacts in the complex formation. Consistently, both of the aforementioned Asf1 mutations also drastically reduced the binding to Cac2C. These results provide a structural basis for a mutually exclusive Asf1-binding model of CAF-1 and HIRA/Hip1, in which Asf1 and CAF-1 assemble histones H3/H4 (H3.1/H4 in vertebrates) in a replication-dependent pathway, while Asf1 and HIRA/Hip1 assemble histones H3/H4 (H3.3/H4 in vertebrates) in a replication-independent pathway.