Women are underrepresented in many science, technology, engineering, and mathematics (STEM) majors and in some non-STEM majors (e.g., philosophy). Combining newly gathered data on students' perceptions of college major traits with data from the Education Longitudinal Study of 2002 (ELS:2002), we find that perceived gender bias against women emerges as the dominant predictor of the gender balance in college majors. The perception of the major being math or science oriented is less important. We replicate these findings using a separate sample to measure college major traits. Results suggest the need to incorporate major-level traits in research on gender gaps in college major choices and the need to recognize the impact of perceptions of potential gender discrimination on college major choices.