E-government challenges are well researched in literature and well known by governments. However, being aware of the challenges of e-government implementation is not sufficient, as challenges may interrelate and impact each other. Therefore, a systematic analysis of the challenges and their interrelationships contributes to providing a better understanding of how to tackle the challenges and how to develop sustainable solutions. This paper aims to investigate existing challenges of e-government and their interdependencies in Tanzania. The collection of e-government challenges in Tanzania is implemented through interviews, desk research and observations of actors in their job. In total, 32 challenges are identified. The subsequent PESTEL analysis studied interrelationships of challenges and identified 34 interrelationships. The analysis of the interrelationships informs policy decision makers of issues to focus on along the planning of successfully implementing the existing e-government strategy in Tanzania. The study also identified future research needs in evaluating the findings through quantitative analysis.