The grain microstructure and damage mechanisms at the grain level are the key factors that influence fatigue of metals at small scales. This is addressed in this work by establishing a new micro-mechanical model for prediction of multiaxial high cycle fatigue (HCF) at a length scale of 5-100mim. The HCF model considers elasto-plastic behavior of metals at the grain level and microstructural parameters, specifically the grain size and the grain orientation.