This study evaluates the trace metal composition and fractionation in sludge samples from anaerobic sewage treatment plants from six cities in Brazil. Ten metals were evaluated: Ni, Mn, Se, Co, Fe, Zn, K, Cu, Pb and Cr. Specific methanogenic activity of the sludge was also evaluated using acetic acid as the substrate. Among the essential trace metals for anaerobic digestion, Se, Zn, Ni and Fe were found at a high percentage in the organic matter/sulfide fraction in all sludge samples analyzed. These metals are less available for microorganisms than other metals, i.e., Co and K, which were present in significant amounts in the exchangeable and carbonate fractions. Cu is not typically reported as an essential metal but as a possible inhibitor. One of the samples showed a total Cu concentration close to the maximal amount allowed for reuse as fertilizer. Among the non-essential trace metals, Pb was present in all sludge samples at similar low concentrations and was primarily present in the residual fraction, demonstrating very low availability. Cr was found at low concentrations in all sludge samples, except for the sludge from STP5; interestingly, this sludge presented the lowest specific methanogenic activity, indicating possible Cr toxicity.