Motivated by recent experimental observation of spin-orbit coupling in carbon nanotube quantum dots [F. Kuemmeth, Nature (London) 452, 448 (2008)], we investigate in detail its influence on the Kondo effect. The spin-orbit coupling intrinsically lifts out the fourfold degeneracy of a single electron in the dot, thereby breaking the SU(4) symmetry and splitting the Kondo resonance even at zero magnetic field. When the field is applied, the Kondo resonance further splits and exhibits fine multipeak structures resulting from the interplay of spin-orbit coupling and the Zeeman effect. A microscopic cotunneling process for each peak can be uniquely identified. Finally, a purely orbital Kondo effect in the two-electron regime is also predicted.