Friction stir welding (FSW) is a solid-state welding process capable of joining a wide range of light metals. However, liquation and solidification may occur during joining of dissimilar metals which leads to eutectic formation. This article aims to discover the influence of tool rotation speed on the formation of eutectic structure during friction stir welding of aluminum to magnesium. To do so, friction stir welding was performed at 600 and 950 rpm to join pure aluminum and ECO-AZ91 magnesium alloy in a lap configuration. In order to investigate the influence of the welding speed, the welding speeds of 23.5 and 37.5 mm/min were also chosen. Scanning electron microscopy (SEM) was used to study the microstructure of the joints. A shear-tensile test was used to evaluate the joints’ strengths. The fracture surfaces were also studied by SEM. The results revealed that changing the rotation speed directly affects the eutectic formation, whereas the welding speed had no influence. A lower rotation speed resulted in a thin, continuous intermetallic layer, whereas a higher speed led to the formation of a massive Mg-Al12Mg17 eutectic microstructure. The formation of eutectic, as an indicative of liquation, may affect the material flow during the process due to decreasing the friction coefficient between the tool and material. The macrostructure analyses showed that the phase evolution as well as the mechanism of material flow are highly affected by liquation.