Ciguatera fish poisoning (CFP) is a common intoxication associated with the consumption of reef fish, which constitutes a critical issue for public health in many countries. The complexity of its epidemiology is responsible for the poor management of the risk in tropical fish markets. We used the example of the Noumea fish market in New Caledonia to develop a cost-effective methodology of assessing the CFP risk. We first used published reports and the knowledge of local experts to define a list of potentially poisonous local species, ranked by their ciguatoxic potential. Based on two 1-month surveys in the market, conducted in winters 2008 and 2009, we then calculated the consolidated ratio of biomass of potentially poisonous species vs. total biomass of fish sold on the market. The prevalence of high CFP-risk species in the market was 16.1% and 18.9% in 2008 and 2009, respectively. The most common high CFP risk species were groupers (serranids), king mackerels (scombrids), snappers (lutjanids), barracudas (sphyaraenids), emperors (lethrinids) and wrasses (labrids). The size (age) of the fish also plays a critical role in the potential ciguatoxic risk. According to proposals of average size thresholds provided by experts for high-risk species, we were also able to assess the additional risk induced by the sale of some large fish on the market. The data collected both from experts and from the market allowed us to develop a cost-effective proposal for improving the management of the CFP risk in this market. However, the successful implementation of any regulation aiming to ban some specific species and sizes from the market, with an acceptable economical impact, will require the improvement of the expertise in fish identification by public health officers and, ideally, the commitment of retailers.