Health is crucial for development, and well-working health information systems are required for sound decision making and effective use of resources. However, establishing working information systems in developing countries is truly a challenge. Moreover, strategies for the development and integration of large and growing collections of information systems escape simplistic recipes. This is a pressing practical problem globally, as well as analytically under-researched within the IS field. We aim to contribute to the understanding and development of such strategies by underscoring two core dilemmas: (i) the conservative influence of historically accumulated and institutionalized practices, technologies and perceptions (dubbed the ‘historicity’ of information systems) and (ii) the lacking integration and increasing fragmentation across the collection of information systems (dubbed the ‘heterogeneity’ of information systems). The empirical underpinning for our analysis is an action research project, the Health Information Systems Program (HISP), which aims at improving existing suboptimal health information systems in developing countries. HISP provides a particularly poignant illustration of the challenges related to historicity and heterogeneity of information systems as these are implied in the politico-historical context. Our empirical material is a cross-national comparative analysis of the current reporting systems for administrative health data in Mozambique, Tanzania and in the state of Andhra Pradesh in India. Several problems are associated with the existing systems and the need to change or replace them is recognized. For example, due to the donor- and aid-dependent economies of most developing countries, there are often other specialized health care programs e.g. targeted towards specific diseases like malaria, tuberculosis and HIV/AIDS. These programs usually have their own reporting systems, and the result emerging over time is a disintegrated and heterogeneous collection of systems. The challenges associated with attempting to change such large-scale, heterogeneous and fragmented systems involve complex dilemmas. As the current information systems are embedded and institutionalized nationwide, a realistic strategy need to take a phased approach whereby present systems are gradually integrated into the environment. In the case of donor-supported and -managed program, the national health authorities may not even have the required power to intervene. Thus the existing reality cannot be ignored or done away with, whether it be the information systems, the institutions or the work practices; they constitute the point of departure. Analytically, we draw on recent socio-technical conceptualizations of large, integrated systems - so-called information infrastructures - especially through recent elaborations in the theoretical foundation in actor-network theory (ANT). The development strategy we suggest emphasizes an evolutionary, ‘cultivating’ approach while at the same time accepting that there will be a certain level of non-integration (often perceived of as ‘mess’) as chronic.