Scanning transmission electron microscopy and density functional theory are used to characterize atomic structures of nanoscale heterointerfaces between gold nanoparticles and a TiO2 (110) surface. It is found that when the gold nanoparticle size is smaller than a few nanometers, gold atoms preferentially attach to specific sites on the TiO2 surface and thus form an epitaxial and coherent heterointerface. Conversely, as the gold size becomes larger, the gold-TiO2 interface loses lattice coherency in order to accommodate the large lattice mismatch between the two dissimilar crystals.