Increased access to mobile technologies has significantly contributed to almost all types of work, including informal work. Mobile phones are one such technology that has been exponentially adopted and used by street traders. However, there is limited information about how street traders use mobile phones to search for new markets. This study investigated street traders’ mobile usage for new market search in Dodoma, Tanzania. Qualitative data were collected using in-depth interviews with 29 street traders, followed by a focus group discussion with eight street traders. Thematic analysis was used to analyze the data. The results show that using mobile phones to search for new markets is scarcely practiced due to certain challenges, such as high costs, technical problems, misuse of mobile contacts by customers, and a concentration of similar products in one location. The findings call for a reduction of mobile service costs, improvement of mobile infrastructure, and provision of education to street traders and customers so that they learn how to use mobile phones for business communication more effectively as well as to abide by communication ethics.