The R₂PdSi₃ intermetallic compounds have been reported to crystallize in a hexagonal AlB₂-derived structure, with the rare earth atoms on the Al sites and Pd and Si atoms randomly distributed on the B sites. However, the intricate magnetic properties observed in the series of compounds have always suggested complications to the assumed structure. To clarify the situation, x-ray and neutron diffraction measurements were performed on the heavy rare earth compounds with R=Gd, Tb, Dy, Ho, Er, Tm, which revealed the existence of a crystallographic superstructure. The superstructure features a doubled unit cell in the hexagonal basal plane and an octuplication along the perpendicular c direction with respect to the primitive cell. No structural transition was observed between 300 and 1.5 K. Extended x-ray absorption fine structure (EXAFS) analysis as well as density functional theory (DFT) calculations were utilized to investigate the local environments of the respective atoms. In this paper the various experimental results will be presented and it will be shown that the superstructure is mainly due to the Pd-Si order on the B sites. A structure model will be proposed to fully describe the superstructure of Pd-Si order in R₂PdSi₃. The connection between the crystallographic superstructure and the magnetic properties will be discussed in the framework of the presented model.