User data fuel the digital economy, while individual privacy is at stake. Governments react differently to this challenge. Estonia, a small Baltic state, has become a role model for the renewal of the social contract in times of big data. While e-governance usage has been growing in many parts of Europe during the last ten years, some regions are lagging behind. The Estonian example suggests that online governance is most accepted in a small state, with a young population, trustworthy institutions and the need of technological renewal. This work examines the development of e-governance usage (citizens interacting digitally with the government) during the last decade in Europe from a comprehensive cross-country perspective: size, age and trust are relevant for the usage of digital government services in Europe. However, the quality of past communication infrastructure is not related to e-governance popularity.