Systems with spin-orbit coupling have the potential to realize exotic quantum states which are interesting both from fundamental and technological perspectives. We investigate the physics that arises when a correlated spin-1/2 quantum impurity hybridizes with a spin-orbit coupled Fermi system. The intriguing aspect uncovered is that, in contrast to unit local moments in conventional systems, the impurity here develops a fractional local moment of 2/3. The concomitant Kondo effect has a high Kondo temperature (T-K). Our theory explains these features including the origins of the fractional local moment and provides a recipe to use spin-orbit coupling (lambda) to enhance the Kondo temperature (T-K similar to lambda(4/3)). Even as our finding of such rich phenomena in a simple looking many-body system is of interest in itself, we also point out opportunities for systems with tunable spin-orbit coupling (such as cold atoms) to explore this physics.