While many studies have discussed the impacts of electronic government (e-government) on public libraries, little research has considered the extent to which the current federal government's implementation of e-government relies on the public technology access, training, and support provided by public libraries. A range of data and policy materials are drawn upon in order to illuminate the co-evolution of public libraries and e-government. Beginning with a discussion of the development of e-government and its impacts in public libraries, the access, goals, and challenges of e-government are detailed as they relate to libraries, and the areas in which current implementations of e-government would not be possible without public libraries. Based on the explorations of the co-evolution of e-government and public libraries, key policy issues are offered that require reconceptualization in order to better support the interrelationship between e-government and public libraries.