This paper presents the rationale for designing and implementing the next-generation of public health information systems using grid computing concepts and tools. Our attempt is to evaluate all grid types including data grids for sharing information and computational grids for accessing computational resources on demand. Public health is a broad domain that requires coordinated uses of disparate and heterogeneous information systems. System interoperability in public health is limited. The next-generation public health information systems must overcome barriers to integration and interoperability, leverage advances in information technology, address emerging requirements, and meet the needs of all stakeholders. Grid-based architecture provides one potential technical solution that deserves serious consideration. Within this context, we describe three discrete public health information system problems and the process by which the Utah Department of Health (UDOH) and the Department of Biomedical Informatics at the University of Utah in the United States has approached the exploration for eventual deployment of a Utah Public Health Informatics Grid. These three problems are: i) integration of internal and external data sources with analytic tools and computational resources; ii) provide external stakeholders with access to public health data and services; and, iii) access, integrate, and analyze internal data for the timely monitoring of population health status and health services. After one year of experience, we have successfully implemented federated queries across disparate administrative domains, and have identified challenges and potential solutions concerning the selection of candidate analytic grid services, data sharing concerns, security models, and strategies for reducing expertise required at a public health agency to implement a public health grid.