In this article, I explore how immigrants from the West African nation of Guinea-Bissau living in Portugal use mobile phones in their daily lives in Lisbon. Whereas one might assume that mobile phones and other new information technologies facilitate transnational communication between Africa and Portugal, the ethnographic fieldwork that I conducted in Lisbon from 1999 to 2003 revealed a different scenario. Instead, mobile phones as imagined and used by the Guinean immigrants I met in Lisbon revealed less about transnationalism and globalization than they did about constructing community and identity in a new locale. As Guinean immigrants in Portugal reconfigured their relationship to their former colonizers and struggled to make their way in a new, multicultural Europe, they used their mobile phones to engage local networks, shape local identities, and transform Lisbon’s sprawl into an African migrant village. Here, I highlight the gendered dimensions of this process and contend that Guinean men’s and women’s varied uses of mobile phones in Lisbon underscore contrasting experiences of migration, mobility, and belonging.