Due to their confidence and dominance, narcissistic leaders oftentimes can be perceived favorably by followers, in particular during times of uncertainty. In this study, we propose and examine the relationship between narcissistic leaders and followers who are prone to experience uncertainty intensely and frequently in general, namely highly anxious followers. We do so by applying machine learning algorithms to account for personality traits in a large sample of leaders and followers on Twitter. We find that highly anxious followers are more likely to interact with narcissistic leaders in general, and male narcissistic leaders in particular. Finally, we also examined these interactions in the context of highly popular leaders and found that as leaders become more popular, they begin to attract less anxious followers, regardless of leader gender. We interpret and discuss these findings in relation to previous work and outline limitations and future research recommendations based on our approach.