We consider the problem of deciding whether two matrices are conjugate. If the coefficient ring is a field, this problem can be easily solved by using the Jordan normal form or the rational canonical form. For more general coefficient rings, the situation becomes increasingly challenging, both from a theoretical and a practical viewpoint. In this talk, we show how the conjugacy problem for integer matrices can be efficiently decided using techniques from group and number theory. This is joint work with Bettina Eick and Eamonn O'Brien.