This study examined how and when employee perceptions of change fairness increase their engagement in innovative behavior during organizational change. Drawing upon fairness heuristic theory, we suggest that change fairness plays a pivotal role as a key heuristic about trustworthiness of leaders and managers in motivating employees to engage in innovative behavior. We also suggest that this change fairness effect becomes stronger or weaker depending on social contexts (change norms, change norm strength, and status differentiation) within a group. Our findings from survey data (N = 318; 35 teams) supported our hypotheses, showing that change fairness is positively related to innovative behavior and that this relationship becomes weaker when (a) group members demonstrate supportive behaviors for the planned change on average (positive change norms), (b) all group members uniformly demonstrate change-supportive behaviors (strong change norms), and (c) group members’ social status perceptions are similar (low status differentiation). We provide insights into theory development and change implementation in practice by highlighting the crucial role of fairness as a key decision heuristic about the trustworthiness of management and demonstrating how social contexts substitute the fairness effect on innovative behavior.