The feasibility of creating atomic wires on vicinal silicon surfaces via pseudomorphic step-edge decoration has been analyzed for the case of Ga on Si(112). Scanning tunneling microscopy and density functional theory calculations indicate the formation of Ga zigzag chains intersected by quasiperiodic vacancy lines or "misfit dislocations." This structure strikes a balance between the system's drive towards chemical passivation and its need for strain relaxation in the atom chains. Spatially fluctuating disorder, intrinsic to the reconstruction, originates from the two symmetry-degenerate orientations of the zigzag chains on vicinal Si.