This investigation probed for anammox bacterial populations that would be suitable to start-up a biological reactor for N-removal. Samples of sludge and sediments from different environments were screened and used as inoculum for enrichment of anammox bacteria in batch cultures. Enrichments were monitored in order to detect anammox bacteria or their potential activity. Candidatus "Brocadia anammoxidans" was successfully enriched, detected, and identified in five of the twelve batch cultures. Furthermore, this organism was retrieved for the first time from a brackish environment. Wide-range primers used in several Polymerase Chain Reaction (PCR) attempts were unable to successfully amplify the 16S rRNA sequence from anammox populations, but were used to search for hypothetical ecological partners of anammox. A nested PCR approach with specific primers was also employed since conventional PCR was unable to amplify anammox DNA from the inocula of the successful enrichments. However, it was impossible to obtain optimal results with the different strategies utilized to improve PCR performance (higher annealing temperature or more specific primers), and only the primer set Amx368F-Amx820R resulted in an acceptable balance between both specificity and sensitivity. Although the enrichment process is relatively slow and requires lengthy incubation periods, it proved to be useful as the molecular analyses were not sensitive enough to detect anammox in the original samples or even after short enrichment periods. Therefore, a batch enrichment procedure coupled with molecular techniques was an appropriate approach to achieve successful inocula for starting-up anammox biological reactor.