There are two connected questions about moral agency and robots: How can we ensure that robots behave in accordance with relevant ethical considerations? Is it possible to have genuinely moral machines? I will approach these questions from an evolutionary perspective and argue for the importance of a middle-range perspective on the morality of machines: we should neither be restricted to the present-day perspective of current ethical concerns nor to the far future theoretical issues concerning the possibility of genuine morality. Instead, we should reflect on what it would mean to create protomoral machines. The evolution of human morality may help in this.