We have identified a paradox in the still low adoption of e-government after more than two decades of policy efforts and public investments for the deployment of online public services. Using as evidence the focus and evolution of this focus over the period 1994–2013 in a vast body of literature produced by academia, international organisations and practitioners, we show that: a) the deployment of e-government was for a long time concentrated on more technological and operational matters and that only more recently attention switched to broadly defined institutional and political issues (hypothesis 1a); and b) institutional and political barriers are one of the main factors explaining lack of e-government adoption (hypothesis 1b). A decision making process that is still unstructured, untrustworthy, and not fully leveraging the available evidence hinder the perception of public value and citizens’ trust in government, which contribute to low level of e-government adoption. We conclude suggesting that a smart government producing public value is grounded in a triangle of good decision defined by politics, values, and evidence and that to achieve it public sector should go beyond the traditional concept of service innovation. It should rather introduce conceptual and systemic innovation pertaining to a new way of thinking and of interacting with stakeholders and citizens as sources of both legitimacy and evidence.