This paper was a subset report of a research project on skill-based English learning strategies by Indonesian EFL learners. It focusses on the attempts to reveal: (1) the differences in the use of strategies of learning speaking skill by male and female learners, and (2) the contribution of strategies of learning speaking skill on the learners’ speaking proficiency. The data from 595 second year senior high school students from eleven schools in East Java, Indonesia were collected using a 70 item questionnaire of Oral Communication Learning Strategy (OCLS) and a 10 item self-assessment of speaking proficiency. The statistical analysis revealed that gender provided significant effects on the intensity of use of six types of strategies of learning speaking skill – interactional-maintenance, self-evaluation, fluency-oriented, time gaining, compensation, and interpersonal strategies – with female learners reporting higher intensity of use. A further analysis found that four strategy types – interactional-maintenance, self-improvement, compensation, and memory strategies – greatly contribute to the speaking proficiency. These findings imply that strategies-based instruction, covering the four most influential strategies, needs to be integrated explicitly in the speaking class to help learners, particularly male learners, cope with problems in learning speaking skill.