Layered van der Waals (vdW) materials grown by physical vapor deposition techniques are generally assumed to have a weak interaction with the substrate during growth. This leads to films with relatively small domains that are usually triangular and a terraced morphology. In this paper, we demonstrate that Bi2Se3, a prototypical vdW material, will form a nano-column morphology when grown on GaAs(001) substrates. This morphology is explained by a relatively strong film/substrate interaction, long adatom diffusion lengths, and a high reactive selenium flux. This discovery paves the way toward growth of self-assembled vdW structures even in the absence of strain.