Bio-Detection Dogs (BDDs) are used in some high-income countries as a diagnostic intervention, yet little is known about their potential in low/middle-income countries with limited diagnostic resources. This exploratory study investigated the opportunities and implications of deploying BDDs as a mobile diagnostic intervention to identify people with asymptomatic malaria, particularly at ports of entry, as an important step to malaria elimination in a population. A qualitative study design consisting of participant observation, five focus group discussions and informal conversations was employed in The Gambia in April-May 2017. A disciplined German Shepherd companion dog (not trained as a BDD) was introduced to research participants and their perceptions recorded. Field-notes and discussions were transcribed, translated and analysed thematically. Most research participants viewed positively the possibility of using BDDs to detect malaria, with the major advantage of being non-invasive. Some concerns, however, were raised regarding safety and efficacy, as well as cultural issues around the place of dogs within human society. The Gambia is a rabies-endemic country, and unfamiliar dogs are not usually approached, with implications for how research participants perceived BDDs. Understanding such concerns and working with local people to address such issues must be part of any successful strategy to deploy BDDs in new settings. Bio-Detection Dogs represent a potentially non-invasive diagnostic tool for the detection of asymptomatic or chronic malaria infections, particularly in areas with very low parasite rates. However, it is important to understand local concerns and work closely with communities to address those concerns. Wider deployment of BDDs will also require careful planning and sustained financial support.