We define the conjugacy graph of a Coxeter system (W,S) so that the connected components correspond to the conjugacy classes of W, and the strongly connected components correspond to a natural equivalence relation on W. This turns the equivalence classes into a graded poset, and we investigate when a conjugacy class is a meet-semilattice. When this happens, there is a natural combinatorial characterization of the conjugacy classes via an equivalence relation on labeled heaps. This is joint work with Dana Ernst and Richard Green.