The tropical shrimp genus Synalpheus includes the only eusocial marine animals. In much of the Caribbean, eusocial species have dominated the diverse fauna of sponge-dwelling shrimp in coral rubble for at least the past two decades. Here we document a recent, dramatic decline and apparent local extinction of eusocial shrimp species on the Belize Barrier Reef. Our collections from shallow reefs in central Belize in 2012 failed to locate three of the four eusocial species formerly abundant in the area, and showed steep declines in colony size and increases in frequency of queenless colonies prior to their disappearance. Concordant with these declines, several nonsocial, pair-forming Synalpheus species increased in frequency. The decline in eusocial shrimp is explained in part by disappearance of two sponge species on which they specialize. Eusocial shrimp collections from Jamaica in 2012 showed similar patterns of decline in colony size and increased queenlessness compared with prior Jamaican collections. The decline and local extinction of eusocial shrimp happened against a backdrop of changes in coral assemblages during recent decades, and may reflect changes in abundance and quality of dead coral substratum and succession of the diverse cryptic organisms living within it. These changes document potentially worrisome declines in a unique taxon of eusocial marine animals.