Recent developments in detection and enumeration of histamine-producing bacteria (HPB) have created powerful molecular-based tools to better understand the presence of spoilage bacteria and conditions, resulting in increased risk of scombrotoxin fish poisoning. We examined 235 scombrotoxin-forming fish from the Gulf of Mexico for the presence of high HPB. Photobacterium damselae subsp. damselae was the most prevalent HPB (49%), followed by Morganella morganii (14%), Enterobacter aerogenes (4%), and Raoultella planticola (3%). The growth characteristics and histamine production capabilities of the two most prevalent HPB were further examined. M. morganii and P. damselae had optimum growth at 35°C and 30 to 35°C and 0 to 2% and 1 to 3% NaCl, respectively. P. damselae produced significantly (P < 0.001) higher histamine than M. morganii in inoculated mahimahi and Spanish mackerel incubated at 30°C for 24 h, but histamine production was not significantly different between the two HPB in inoculated tuna, possibly due to differences in muscle composition and salt content. Results in this study showed that P. damselae was the most prevalent high HPB in Gulf of Mexico fish. In addition, previously reported results using the traditional Niven's method may underreport the prevalence of P. damselae. Molecular-based methods should be used in addition to culture-based methods to enhance detection and enumeration of HPB.