One of the basic problems in ergodic theory is to determine when two measure-preserving transformations of the atomless Borel probability space are orbit equivalence. Since any two such actions of an amenable group are orbit equivalent by classical results of Dye and Ornstein-Weiss, the question is relevant only in the non-amenable case. In this direction, we show that, for every nonamenable countable discrete group, the relations of conjugacy and orbit equivalence of free ergodic actions are not Borel, thus answering questions of Kechris. The statement about conjugacy solves the nonamenable case of Halmos' conjugacy problem in Ergodic Theory, originally posed in 1956 for ergodic transformations.