We report the phase and microstructure evolution of the Cu-13 wt.% Al mixture during treatment in a high-energy planetary ball mill with a particular focus on the early stages of mechanical alloying. Several characterization techniques, including X-ray diffraction phase analysis, nuclear magnetic resonance spectroscopy, differential dissolution, thermal analysis, and electron microscopy/elemental analysis, have been combined to study the evolution of the phase composition of the mechanically alloyed powders and describe the microstructure of the multi-phase products of mechanical alloying at different length scales. The following reaction sequence has been confirmed: Cu + Al → CuAl2(+Cu) → Cu9Al4 + (Cu) → Cu(Al). The phase evolution was accompanied by the microstructure changes, the layered structure of the powder agglomerates disappearing with milling time. This scheme is further complicated by the processes of copper oxidation, reduction of copper oxides by metallic aluminum, and by variation of the stoichiometry of Cu(Al) solid solutions with milling time. Substantial amounts of X-ray amorphous phases were detected as well. Differential dissolution technique has revealed that a high content of aluminum in the Cu(Al) solid solution-based powders is due to the presence of Al-rich phases distributed between the Cu(Al) crystallites.