This study evaluated the association between Internet addiction and frustration intolerance, the gender difference of frustration intolerance, and the gender differences of the association between Internet addiction and frustration intolerance. Participants were 2,114 students (1,204 male and 910 female) who were recruited to complete the Chen Internet Addiction Scale and Frustration Discomfort scale. Females had higher scores on the subscale of entitlement and emotional intolerance and the total scale of the frustration intolerance. There was a significant gender difference on the association between Internet addiction and frustration intolerance. The association was higher in male adolescents. Regression analysis revealed male adolescents with Internet addiction had higher intolerance to frustration of entitlement and emotional discomfort, and female adolescents with it had higher intolerance to emotional discomfort and lower tolerance to frustration of achievement. Frustration intolerance should be evaluated for adolescents with Internet addiction, especially for males. Rational emotive behavior therapy focusing on different irrational beliefs should be provided to male and female adolescents with Internet addiction.