Motivated by the growing interest in the novel quantum phases in materials with strong electron correlations and spin–orbit coupling, we study the interplay among the spin–orbit coupling, Kondo interaction, and magnetic frustration of a Kondo lattice model on a two-dimensional honeycomb lattice. We calculate the renormalized electronic structure and correlation functions at the saddle point based on a fermionic representation of the spin operators. We find a global phase diagram of the model at half-filling, which contains a variety of phases due to the competing interactions. In addition to a Kondo insulator, there is a topological insulator with valence bond solid correlations in the spin sector, and two antiferromagnetic phases. Due to the competition between the spin–orbit coupling and Kondo interaction, the direction of the magnetic moments in the antiferromagnetic phases can be either within or perpendicular to the lattice plane. The latter antiferromagnetic state is topologically nontrivial for moderate and strong spin–orbit couplings.