Palladium, vapor-deposited at room temperature on a reduced SnO$_2$(101) surface, forms one-dimensional islands, one atomic layer high, 5 Å wide, and up to 350 Å long. Scanning tunneling microscopy shows that neighboring islands do not merge. First-principles calculations reveal the atomistic processes that lead to this, for metal oxide substrates unusual, overlayer growth. Formation of 1D islands is mediated by a large anisotropy in surface diffusion, strong Pd-Sn interaction, and the lack of stable binding sites at the sides of the Pd islands. Nucleation is defect mediated, and the initial nucleation site determines the width of the resulting nanocluster.