This study examines the relationships between employees’ cultural value orientations and their innovative work behaviors and the mediation effects of self-leadership in the relationships. Four hundred and eighty two employees working at various firms in Korea and China responded to a questionnaire consisting of measures designed to assess uncertainty avoidance, power distance, and innovative work behavior. Analyses of the data revealed that power distance was negatively related to innovative work behavior for both respondents while uncertainty avoidance was positively related to innovative work behavior. The mediation effects of self-leadership were also found. This study contributes to current research literature by providing empirical evidence for the role of self-leadership in the mechanism linking individuals’ cultural value orientations and innovative work behavior. The study also discusses similarities and differences in the patterns of power distance, uncertainty avoidance, innovative work behavior, and self-leadership across Korean and Chinese respondents and their implications in changing business environment.