The Web now provides instant access to an unprecedented amount of information that was unthinkable even 20–30 years ago. However, the full potential of the contents available through the Internet can only be realized when one can speak the lingua franca online, English. According to a recent survey (Web Technology Surveys, 2015), more than 55% of web contents are in English. Previous studies have shown that non-native speakers’ English proficiency affects their searching behaviors and performance (Bilal, 1989, Liao, Finn & Lu, 2007, Onwuegbuzie & Jiao, 1997). In this study, we try to investigate the effect of search task languages and task complexity on searching performance. In other words, we want to understand the extent to which the use of a foreign language becomes a barrier – when one’s native language is not English but one has to use English for searching on the Web for personal or work related tasks.