Certain classes of supersymmetric Yang-Mills (SYM) theories including the well known N=4 SYM, that takes part in the AdS/CFT correspondence, can be formulated on the lattice using the techniques of exact lattice supersymmetry. In this talk I will provide the construction of such theories and describe how great ideas such as topological field theories, Dirac-Kahler fermions, geometric discretization all come together to create lattice SYM theories that are exact-supersymmetric, gauge-invariant and doubler-free on the lattice. Then I move on to discuss the one-loop renormalization of N=4 SYM on the lattice, restoration of the full set of supersymmetries, sign problem in these theories and also lattice study of finite temperature phase transitions in SYM theories and their connections to some black hole solutions in dual supergravity theories.