Program monitoring and evaluation (M&E) has the potential to be a cornerstone of health systems strengthening and of evidence-informed implementation and scale-up of HIV-related services in resource-limited settings. We discuss common challenges to M&E systems used in the rapid scale-up of HIV services as well as innovations that may have relevance to systems used to monitor, evaluate, and inform health systems strengthening. These include (1) Web-based applications with decentralized data entry and real-time access to summary reporting; (2) timely feedback of information to site and district staff; (3) site-level integration of traditionally siloed program area indicators; (4) longitudinal tracking of program and site characteristics; (5) geographic information systems; and (6) use of routinely collected aggregate data for epidemiologic analysis and operations research. Although conventionally used in the context of vertical programs, these approaches can form a foundation on which data relevant to other health services and systems can be layered, including prevention services, primary care, maternal-child health, and chronic disease management. Guiding principles for sustainable national M&E systems include country-led development and ownership, support for national programs and policies, interoperability, and employment of an open-source approach to software development.