Many exoplanetary systems containing hot Jupiters are observed to have highly misaligned orbital axes relative to the stellar spin axes. Kozai-Lidov oscillations of orbital eccentricity and inclination induced by a binary companion, in conjunction with tidal dissipation, constitute a major channel for the production of hot Jupiters. We demonstrate that gravitational interaction between the planet and its oblate host star can lead to chaotic evolution of the stellar spin axis during Kozai cycles. As parameters such as the planet mass and stellar rotation period are varied, periodic islands can appear in an ocean of chaos, in a manner reminiscent of other dynamical systems. In the presence of tidal dissipation, the complex spin evolution can leave an imprint on the final spin-orbit misalignment angles.