The giga-cycle property of a newly developed Al alloy, which contains 0.5wt.% excess Mg solute compared to a standard age-hardened 6061 alloy (6061-T6), was investigated by using smooth specimens subjected to ultrasonic fatigue. The fatigue strength of the new alloy was higher than that of a normal 6061 alloy particularly at relatively low stress amplitude level. Several analyses (surface crack observation, fractography, FIB cross-sectioning, etc.) were also conducted to reveal the micro-mechanism of the observed strength properties. The following results were obtained: i) No fatigue limit was confirmed for both 6061 and new alloy. ii) Total life (Nf) of 6061 and new alloys was determined by a single fatigue crack initiated from a surface PSB crack. iii) Crack initiation resistance defined by N25 (number of cycles to reach ρ = 25 mm-2, where ρ is the PSB crack number density) for new alloy was higher than that of 6061. iv) The higher fatigue strength of new alloy was explained by the effect of excess Mg solute which increased the resistance against the formation of PSB cracks.