In this paper, we describe hardware for inference computations on Markov Random Fields (MRFs). MRFs are widely used in applications like computer vision, but conventional software solvers are slow. Belief Propagation (BP) solvers, which use patterns of local message passing on MRFs, have been studied in hardware, but their performance is unreliable. We show how a superior method—Sequential Tree-Reweighted message passing (TRW-S)—can be rendered in hardware. TRW-S has reliable convergence, guaranteed by its so-called “sequential” computation. Analysis reveals many opportunities for TRW-S hardware acceleration. We show how to implement TRW-S in FPGA hardware so that it exploits significant parallelism and memory bandwidth. Our implementation is capable of running a standard stereo vision benchmark at rates approaching 40 frames/sec; this represents the first time TRW-S methods have been accelerated to these speeds on an FPGA platform.