This study reports on the current English language learning strategies used by Arabic-speaking English-majors enrolled at An-Najah National University in Palestine. The subjects of the study were (99) male and female students still studying for their B.A. degree. The study also investigates the frequency of strategies use among these students according to gender and proficiency variables. Proficiency is reflected by students’ learning level (i.e. sophomore, junior, senior), self-reported proficiency in English (i.e. the students’ university average in English courses) and language self-efficacy (i.e. how good the students perceived themselves as English learners). The results of this study showed that An-Najah English majors used learning strategies with high to medium frequency, and that the highest rank (79.6%) was for Metacognitive strategies while the lowest (63%) was for compensation strategies. In general, the results showed that gender and proficiency had no significant differences on the use of strategies. Based on these findings, the researcher recommends that more training should be given in using Cognitive, Memory and Compensation strategies by embedding them into regular classroom activities.