Available bandwidth estimation techniques are being used in network monitoring and management tools to provide information about the utilization of the network and verify the compliance of service level agreements. However, the use of these techniques in other applications and network environments is limited by the long convergence times, accuracy errors, and the amount of overhead that they introduce. In this paper, we introduce Traceband, a hidden Markov model-based technique for end-to-end available bandwidth estimation and monitoring that improves these performance metrics and therefore promises to expand the use of these techniques in other scenarios. Traceband is evaluated and compared with Spruce and Pathload using Poisson and self-similar cross-traffic. Experimental results in a controlled environment with Poisson cross-traffic demonstrate that Traceband is as accurate as Spruce and Pathload but considerably faster, and introduces less overhead. Traceband’s convergence time is demonstrated using bursty cross-traffic, as it is the only tool that accurately reacts to zero-traffic periods, which may be particularly useful for those applications that need to make decisions in real time. Using self-similar traffic, Traceband’s mean accuracy and variability degrade with the Hurst parameter but it still performs within reasonable limits. A general and optional moving average algorithm is also introduced to solve these issues.