Underwater dissimilar friction stir welding of the AA6061 and AA7075 aluminum alloys was performed in this study. The effect of friction stir welding parameters on the grain size and hardness of the joints was studied using empirical models. The microstructure of the joints was characterized by means of light and transmission electron microscopes. The Vickers hardness test was conducted to measure the hardness of the joints. In addition, the process parameters including traverse and rotational speeds, grain size and hardness of the joints were correlated. The results revealed that the developed models predicted the hardness and grain size of the joints, precisely. Higher traverse speed and lower rotational speeds resulted in finer grain size and larger hardness. The grain boundaries and dislocations were identified as responsible for the higher hardness of the joints welded at lower heat input conditions. Moreover, the Hall-Petch relationship showed a deviation from its linear classical equation, which was due to the formation of substructures such as dislocations inside the grains.