Since the summer of 1997, we have sought to develop a methodology that would help us recover non-stone archaeological sites on Pemba Island, Tanzania. What follows is a report of a three-pronged effort to do this, with the hope that our results might be helpful to others working in East Africa. First, we discuss the 1997 excavation of a house that had stood for most of the twentieth century and was razed by its owner in the early 1990s, and shovel-test pits in the vicinity of that house. Second, we present two styles of systematic survey. Around the site of Pujini and modern town of the same name, in central western Pemba, a systematic survey based on one-hundred-percent coverage of particular landforms was carried out in 1997. This was followed in 1998 by a systematic survey based on transects radiating from the site of Chwaka, in northern Pemba. Our purpose here is to focus on what the results of these efforts can tell us about finding the sites themselves, the first critical step in incorporating non-stone sites into the larger picture of Swahili life. It is becoming increasingly evident, that the richness of the archaeology at stonetowns notwithstanding, we can only understand the diversity of the Swahili experience by combining the archaeology of the Swahili elite — that minority who lived in stone houses in stonetowns — with the archaeology of "the rest". These would be the early villagers, the urban populations living in wattle-and-daub wards of towns, and the villagers throughout the many centuries who interacted with and were tied in various ways to the townspeople. We will consider our three small studies in the context of other work, in Africa and elsewhere, that concerns itself particularly with wattle-and-daub and other less-permanent architecture in both archaeological excavation and survey.