Nanosecond duration, high intensity and high average power laser pulses induce damage on uncoated optics, due to localized field enhancement at the exit surface of the components. Anti-reflection (AR) coated optics, due to their (multiple) thin film boundaries, have similar field enhancement regions, which lead to laser damage on both entry and exit sides. Nano-scale structured optical interfaces with AR performance (ARSS) have been widely demonstrated, and found to have higher laser damage resistance than conventional AR coatings. Comprehensive tests of optical entry and exit structured-surface laser damage using nanosecond pulses for ARSS are not widely available. We measured the laser damage of random anti-reflective surface structures (rARSS), on planar, optical quality, fused silica substrates, using single 6-8ns duration pulses at 1064 nm wavelength. The single-sided rARSS substrates were optimized for Fresnel reflectance suppression at 1064 nm, and the measured transmittance at normal incidence was increased by 3.2%, with a possible theoretical maximum of 3.5%. The high energy laser beam was focused to increase the incident intensity, in order to probe values above and below the damage thresholds reported in the literature. The source laser Q-switch durations were used to directly control incident fluence. Multiple locations were tested for each Q-switch setting, to build a statistical relationship between the fluence and damaging events. Single-sided, AR random surface structured substrates were tested, using entry and exit side orientations, to determine any effects the random structures may have in the damage induced by the field enhancement on the exit side. We found that the AR randomly structured surfaces have a higher resistance, to the onset of laser damage, when they are located at the entry (structured) side of the substrates. In comparison, when the same AR random structures are in the beam exit side of the substrates, the onset of laser damage occurs at lower fluence values. All tests resulting in damage of the optical-quality polished fused silica substrates, and those with the structures on the exit side of the samples, are ballistic in nature, showing surface cracks and outward-directed debris craters, all occurring at the beam exit facet. Of interest are the results from tests completed with the rARSS located on the beam entry side; the damage caused by these tests was not typically ballistic in nature (inward directed craters) and occurred on the structured side of the samples.