A numerical method based on asymptotic homogenization theory is presented for the design of lattice materials against fatigue failure. The method is applied to study the effect of unit cell shape on the fatigue strength of hexagonal and square lattices. Cell shapes with regular and optimized geometry are examined. A unit cell is considered to possess a regular shape if the geometric primitives defining its inner boundaries are joined with an arc fillet, whose radius is 1% of the cell length. An optimized cell shape, on the other hand, is obtained by minimizing the curvature of its interior borders, which are conceived as continuous in curvature to smooth stress localization. For a given multi-axial cyclic loading, failure surfaces of metallic hexagonal and square lattices are provided along with their modified Goodman diagrams to assess the effect of mean and alternating stresses on the fatigue strength. In good agreement with the experimental data available in literature, the numerical results show that the shape of the unit cell has a major impact on the fatigue performance of the lattice material. For example under fully reversible tension, the fatigue strength of optimized square lattices of 10% relative density is shown to be 54% higher than that of their conventional counterparts with regular cell geometry.