The domain structures of annealed (001)-oriented $Pb(Mg_{1/3}Nb_{2/3})O_3-x%PbTiO_3$ (PMN-x%PT) crystals for x = 10, 20, 30, 35, and 40 at% were investigated by Polarized Optical Microscopy (POM) and Scanning Force Microscopy (SFM) in the piezoresponse mode. Both Polar Nano-Domains (PND) and long strip-like domains were clearly observed. The results also showed how the domain structure changed between phases with an increasing x in the PMN-x%PT crystals and the domain hierarchy on various length scales ranging from 40 nm to 0.1 mm. Distorted pseudo-cubic phase (x < 20%) consisted of PNDs that did not self-assemble into macro-domain plates. The rhombohedral phase (x = 30%) consisted of PNDs that began to self-assemble into colonies along preferred {110} planes. The monoclinic phase (x = 35%) consisted of miniature polar domains on the nm scale, whereas, the tetragonal phase (x = 40%) consisted of {001} oriented lamella domains on the mm scale that had internal nano-scale heterogeneities, which self-assembled into macro-domain plates oriented along {001} the mm scale.