Several governments are in the process of implementing e-procurement. In the process they face several challenges. The diffusion of e-procurement in the Danish public sector is researched using case study research methodology to study the challenges faced. The results of the study are applied in this paper for explaining some of the challenges faced using the legacy centralization versus decentralization debates regarding computing and organization; which forms the tale. These debates in no doubt help in kick starting the research on the diffusion of e-procurement in the public sector. However, the phenomenon under study is complex and unique in several respects that the debates alone are inadequate for fully explaining the challenges. The paper presents a question as the twist in the tale answering which helps in understanding the nature of challenges much better. The question is “To what extent is government a single organization?”