Three-quarters of the global mental health burden exists in low- and middle-income countries (LMICs), yet the lack of mental health services in resource-poor settings is striking. Task-sharing (also, task-shifting), where mental health care is provided by non-specialists, has been proposed to improve access to mental health care in LMICs. This multi-site qualitative study investigates the acceptability and feasibility of task-sharing mental health care in LMICs by examining perceptions of primary care service providers (physicians, nurses, and community health workers), community members, and service users in one district in each of the five countries participating in the PRogramme for Improving Mental health carE (PRIME): Ethiopia, India, Nepal, South Africa, and Uganda. Thirty-six focus group discussions and 164 in-depth interviews were conducted at the pre-implementation stage between February and October 2012 with the objective of developing district level plans to integrate mental health care into primary care. Perceptions of the acceptability and feasibility of task-sharing were evaluated first at the district level in each country through open-coding and then at the cross-country level through a secondary analysis of emergent themes. We found that task-sharing mental health services is perceived to be acceptable and feasible in these LMICs as long as key conditions are met: 1) increased numbers of human resources and better access to medications; 2) ongoing structured supportive supervision at the community and primary care-levels; and 3) adequate training and compensation for health workers involved in task-sharing. Taking into account the socio-cultural context is fundamental for identifying local personnel who can assist in detection of mental illness and facilitate treatment and care as well as training, supervision, and service delivery. By recognizing the systemic challenges and sociocultural nuances that may influence task-sharing mental health care, locally-situated interventions could be more easily planned to provide appropriate and acceptable mental health care in LMICs.