In this paper, we present an acoustic direction-of-arrival (DOA) tracking system to track multiple maneuvering targets using a state space approach. The system consists of three blocks: beamformer, random sampling, and particle filter. The beamformer block processes the received acoustic data to output bearing batches as point statistics. The random sampling block determines temporal clustering of the bearings in a batch to determine region-of-interests (ROIs). Based on the track-before-detect approach, each ROI indicates the presence of a possible target. We describe three random sampling algorithms called RANSAC, MSAC, and NAPSAC to use in the random sampling block. The particle filter then tracks the targets via its interactions with the beamformer and the random sampling blocks. We present a computational analysis of the random sampling blocks and show tracking results with field data.