Leadership communication competence is known to be a key element in organizational success. The present study examines leadership communication competence in an institution of higher learning in Malaysia. The study delved into subordinates’ perception of their leaders’ encoding and decoding skills and found that these leaders have a relatively high encoding and decoding skills. When comparing between males and females, it was found that the males scored higher in both skills. This result seems similar to the western literature on gender communication but purportedly with different reasons for why men scored higher than women. This study, thus, contributes to the literature on the influence of culture in relation to the perception of gender communication competence.