Following years of intensive international debate of the ethical and human rights implications of artificial intelligence (AI)-related technologies, there are numerous proposals to legislate and regulate these technologies. One aspect of possible legislative frameworks for AI is the creation of a new regulator or other body with the remit to provide oversight of AI. This article reviews the ethical and human rights challenges as well as proposed mitigation strategies, in order to the discuss how a regulatory body might be designed to address these challenges. It focuses on a particular form that a new body might take, more specifically on a potential European Agency for AI. Based on a multi-step methodology of stakeholder interaction, the article proposes a terms of reference for such an Agency and discusses the characteristics it would need to display to ensure that it could adequately engage with current and future ethical and human rights challenges arising from the development, deployment and use of AI. This proposal is then contrasted with the proposed European Artificial Intelligence Board included in the draft European Regulation on AI (the AI Act).