Innovative work behavior is a vital necessity that enables sustainable public sector organizations, particularly the highly centralized military ones, to successfully adapt to complex and rising challenges. This empirical study, drawing on the social exchange theory, investigates the separate and combined effects of ambidextrous leadership dimensions (i.e., opening and closing leader behaviors) on innovative work behavior and the moderating role of climate for innovation on these relationships. The data were collected from 425 participants working at Allied Command Transformation (ACT), the North Atlantic Treaty Organization's (NATO) Warfare Development Command, and analyzed using AMOS and SPSS Process Macro. We found that while opening leader behavior of ambidextrous leadership was positively related to innovative work behavior, closing leader behavior had no significant effect on it. Findings also confirmed that the interaction of both (i.e., the combined effect of ambidextrous leadership) was positively related to innovative work behavior, and climate for innovation moderated the relations of both closing leader behavior and ambidextrous leadership to innovative work behavior. Based on these results, we discuss the managerial and theoretical implications.