Recent years have seen a rapid growth of evidence suggesting that materials interfaces are capable of first-order structural transformations in which the interface properties undergo discontinuous changes. Experiments have linked these transitions to abnormal grain growth in ceramics, activated sintering and liquid metal embrittlement and raised a number of fundamental questions concerning the atomic structures and kinetic properties of these interface phases. This talk will review recent advances in modeling methodology that enable discovery of grain boundary phases. Applications of this methodology to several materials systems are discussed. This work was performed under the auspices of the U.S. Department of Energy by Lawrence Livermore National Laboratory under Contract DE-AC52-07NA27344.