A semi-automated workflow relying on atomic-scale modelling is introduced to explore and understand the yet-unsolved structure of the crystalline AsTe3 material, recently obtained from crystallization of the parent AsTe3 glass, which shows promising properties for thermoelectric applications. The seemingly complex crystal structure of AsTe3 is investigated with density functional theory, from the stand point of As/Te disorder, in a structural template derived from elemental-Te (Teel), following experimental findings from combined X-ray total scattering and diffraction. Our workflow includes a combinatorial structure generation step followed by successive structure selection and relaxation steps with progressively-increasing accuracy levels and a multi-criterion evaluation procedure. A small set of high quality models with common structural features emerge, all consisting of intergrowth domains typically below 1 nm in thickness and with the local compositions and structures of Teel and α-As2Te3, but with different thicknesses and relative arrangements, which points to the presence of such defects in crystalline AsTe3. While predictions of the electronic bandgaps are in excellent agreement with the experimental value for our best models, we find that some of these defects may be associated with the locally-increased density of states around the Fermi level, potentially contributing to the overall electronic conductivity, which, along with intrinsic structural complexity, is among the key features of the reported outstanding thermoelectric properties of this compound.