We study the effect of coupling magnetic impurities to the honeycomb lattice spin-1/2 Kitaev model in its spin-liquid phase. We show that a spin-S impurity coupled to the Kitaev model is associated with an unusual Kondo effect with an intermediate coupling unstable fixed point Kc∼J/S separating topologically distinct sectors of the Kitaev model. We also show that the massless spinons in the spin-liquid mediate an interaction of the form Siα2Sjβ2/Rij3 between distant impurities unlike the usual dipolar RKKY interaction SiαSjα/Rij3 noted in various 2D impurity problems with a pseudogapped density of states of the spin bath. Furthermore, this long-range interaction is possible only if the impurities (a) couple to more than one neighboring spin on the host lattice and (b) the impurity spin S≠ 1/2. © 2010 The American Physical Society.