This article summarizes a multistate outbreak of heterosexual syphilis, including 134 cases of syphilis in adults and adolescents and at least 2 cases of congenital syphilis, which occurred on an American Indian reservation in the United States during 2013-2015. In addition to providing salient details about the outbreak, the article seeks to document the case-finding and treatment activities undertaken, their relative success or failure, and the lessons learned from a coordinated, multiagency response. Of 134 adult cases of syphilis, 40% were identified by enhanced, interagency contact tracing and partner services, 26% through symptomatic testing, and 16% through screening of asymptomatic individuals as the result of an electronic medical record screening prompt. A smaller proportion of cases were identified by community screening events in high-morbidity communities; high-risk venue-based screening events; other screening, including screening upon request; and prenatal screening at first trimester, third trimester, and day of delivery. Future heterosexual syphilis outbreak responders should act quickly to coordinate a package of high-yield case-finding and treatment activities-potentially including activities that seek to do the following: (1) increase prenatal screening, (2) improve community awareness and symptomatic test seeking, (3) educate providers and improve general screening for syphilis, (4) implement electronic medical record reminders for providers, (5) screen high-morbidity communities and at high-risk venues, and (6) form novel partnerships to accomplish partner services work when the context does not allow for traditional, disease intervention specialist-only partner services.