This study investigates the differences of speaking strategy use by the EFL-major university students in Japan and Bangladesh. EFL speaking strategies were measured by a speaking strategy use questionnaire with items selected, combined and simplified from two sets, Language Strategy Use Survey (Cohen and Chi, received from internet on July 17, 2004) and The Strategy Inventory for Language Learning (SILL) (Oxford, 1990) on 165 EFL-majors, 102 Japanese (70 females and 32 males) and 63 Bangladeshi (26 females and 37 males). To determine the learners' confidence in their own speaking skill levels a self-evaluative format was joined with the questionnaire. The major findings were that the Bangladeshi learners reported more frequent use of cognitive and interpersonal strategies than the Japanese learners. The Japanese females reported more use of cognitive strategy than the males. On the other hand, the Bangladeshi learners showed no gender difference in any category. The Japanese females showed communicative-experiential strategy as the most frequently used category, whereas the males showed almost equal frequency to communicative-experiential, management & planning and interpersonal strategies. The Bangladeshi females reported almost the same frequency to use communicative-experiential, interpersonal, and cognitive strategies and the males showed almost the same tendency including management & planning strategy with the above categories. Cognitive and affective strategies had the strongest correlations with the other categories in both cultures. The Japanese learners' self-evaluation had the strongest correlations with the use of affective and interpersonal strategies. The Bangladeshi learners' self-evaluation had the strongest correlations with the use of cognitive and communicative-experiential strategies. Some pedagogical implications of the findings are discussed along with suggestions for further research.