Micro-compression tests were performed on pre-strained nickel (Ni) single crystals in order to investigate the influence of the initial dislocation arrangement on the size dependence of small-scale metal structures. A bulk Ni sample was grown using the Czochralski method and sectioned into four compression samples, which were then pre-strained to nominal strains of 5, 10, 15 and 20%. Bulk samples were then characterized using transmission electron microscopy (TEM), micro-Laue diffraction, and electron backscatter diffraction. TEM results show that a dislocation cell structure was present for all deformed samples, and Laue diffraction demonstrated that the internal strain increased with increased amount of pre-straining. Small-scale pillars with diameters from 200 nm to 5 μm were focused ion beam (FIB) machined from each of the four deformed bulk samples and further compressed via a nanoindenter equipped with a flat diamond punch. Results demonstrate that bulk pre-straining inhibits the sample size effect. For heavily pre-strained bulk samples, the deformation history does not affect the stress-strain behavior, as the pillars demonstrated elevated strength and rather low strain hardening over the whole investigated size range. In situ TEM and micro-Laue diffraction measurements of pillars confirmed little change in dislocation density during pillar compression. Thus, the dislocation cell walls created by heavy bulk pre-straining become the relevant internal material structure controlling the mechanical properties, dominating the sample size effect observed in the low dislocation density regime.