There is enormous opportunity for positive social impact from the rise of algorithms and machine learning. But this requires a licence to operate from the public, based on trustworthiness. There are a range of concerns relating to how algorithms might be held to account in areas affecting the public sphere. This paper outlines a number of approaches including greater transparency, monitoring of outcomes and improved governance. It makes a case that public sector bodies that hold datasets should be more confident in negotiating terms with the private sector. It also argues that all regulators (not just data regulators) need to wake up to the challenges posed by changing technology. Other improvements include diversity of the workforce, ethics training, codes of conduct for data scientists, and new deliberative bodies. Even if these narrower issues are solved, the paper poses some wider concerns including data monopolies, the challenge to democracy, public participation and maintaining the public interest. This article is part of a discussion meeting issue ‘The growing ubiquity of algorithms in society: implications, impacts and innovations’.