Although paradoxes are inherent to the public sector, few attempts have been made to better understand how to manage such competing yet interrelated demands effectively. This study examines how paradoxical leadership (i.e., leaders’ sense-giving about organizational paradoxes) affects follower outcomes. Based on two-wave survey data from German district offices, structural equation modelling reveals that paradoxical leadership positively influences followers’ job satisfaction and work engagement. Role ambiguity fully mediates the relationship between paradoxical leadership and perceived performance. Our study expands the nomological network of public leadership and advances the notion that paradoxes bear potentials for leadership in ambiguous public settings.