The classical phase diagram of the Kane-Mele-Heisenberg model is obtained using three complementary methods: Luttinger-Tisza, variational minimization, and the iterative minimization method. Six distinct phases were obtained in the space of the couplings. Three phases are commensurate with long-range ordering: planar Néel states in horizontal plane (phase I), planar states in the plane vertical to the horizontal plane (phase VI), and collinear states normal to the horizontal plane (phase II). However, the other three are infinitely degenerate due to the frustrating competition between the couplings, and they are characterized by a manifold of incommensurate wave vectors. These phases are planar helical states in a horizontal plane (phase III), planar helical states in a vertical plane (phase IV), and non-coplanar states (phase V). Employing the linear spin-wave analysis, it is found that the quantum fluctuations select a set of symmetrically equivalent states in phase III through the quantum order-by-disorder mechanism. Based on some heuristic arguments, it is argued that the same scenario may also occur in the other two frustrated phases VI and V.