This study was conducted to determine the concentration of total mercury in the edible portion of 46 species of marine fish (n = 297) collected from selected major fish landing ports and wholesale markets throughout Peninsular Malaysia. Samples were collected in June to December 2009. Prior to analysis, the fish samples were processed which consisted of drying at 65 °C until a constant weight was attained; then, it was grounded and digested by a microwave digestion system. The analytical determination was carried out by using a mercury analysis system. Total mercury concentration among fish species was examined. The results showed that mercury concentrations were found significantly higher (p < 0.001) in demersal fish (the range was from 0.173 to 2.537 mg/kg in dried weight) compared to pelagic fish (which ranged from 0.055 to 2.137 mg/kg in dried weight). The mercury concentrations were also higher in carnivorous fish especially in the species with more predatory feeding habits. Besides, the family group of Latidae (0.537 ± 0.267 mg/kg in dried weight), Dasyatidae (0.492 ± 0.740 mg/kg in dried weight), and Lutjanidae (0.465 ± 0.566 mg/kg in dried weight) showed significantly (p < 0.001) higher mercury levels compared to other groups. Fish collected from Port Klang (0.563 ± 0.509 mg/kg in dry weight), Kuala Besar (0.521 ± 0.415 mg/kg in dry weight), and Pandan (0.380 ± 0.481 mg/kg in dry weight) were significantly higher (p = 0.014) in mercury concentrations when compared to fish from other sampling locations. Total mercury levels were significantly higher (p < 0.002) in bigger fish (body length >20 cm) and were positively related with fish size (length and weight) in all fish samples. Despite the results, the level of mercury in marine fish did not exceed the permitted levels of Malaysian and JECFA guideline values at 0.5 mg/kg methylmercury in fish.