This study illustrates how compliments and compliment response strategies differ across gender among celebrities in Malaysia. The objective of the study is to identify the functions and topics of compliments, and also the patterns and strategies of compliment responses across gender among celebrities on twitter. Forty celebrities consisting of 20 males and 20 females were selected and the data were collected from their twitter accounts. A total of 220 compliments and compliment responses were extracted from the celebrities’ tweets as to form the corpus for investigation. The results indicate several differences on how compliments and compliment responses are used by men and women. Women prefer to compliment on appearance, while men prefer to compliment on possession. The results also reveal differences in strategies used by the celebrities to respond to compliments. Female addressees adhere to the first principle that governed the act of politeness, that is, to accept the compliment in order to give face to the complimenter. However, male addressees tend to use comment acceptance when receiving compliments. The study provides evidence for significant differences in the use of compliments and compliment responses across gender. In addition, cross-cultural differences are also discussed briefly.