The proliferation of non-native fishes in Florida is a serious problem, and new species continue to be introduced to the state. Fishes in the Family Cichlidae have been especially successful colonizers of south Florida freshwater habitats. Herein we report a multi-agency effort to eradicate two non-native cichlid fishes in Miami, Florida (Bay Snook Petenia splendida and Blue Mbuna Labeotropheus fuelleborni). These fishes were removed before they were observed in the extensive, interconnected canal system through which they may have been able to expand throughout south Florida and access protected areas such as Everglades National Park. The study site, Pinecrest Gardens, is important because it contains remnant coastal cypress-strand habitat in an increasingly urbanized landscape that historically provided refuge to native amphidromous fishes and invertebrates. The project took considerable time (3.5 years), and we detail in this report how it evolved from a focus on isolating the non-native fishes and reducing their population sizes to an eradication. Gardens’ staff hydrologically isolated their ponds from nearby waterbodies by plugging a culvert with a solid gate. That provided the interagency team with more time to remove the potential threats. Compromises were made between fish management strategies and the Gardens’ priorities. Hurricane impacts helped shift priorities to more aggressive fish-management strategies. Cooperation among several federal and state agencies, as well as the Gardens, was key to the project’s success. We hope this effort may serve as a model for removing non-native species before they spread into ecosystems where eradication is not practical.