© 2015. American Geophysical Union. All Rights Reserved. California Institute of Technology. Government sponsorship acknowledged. This study presents a new algorithm for parallel computation of river flow that builds on recent work demonstrating the relative independence of distant river reaches in the update step of the Muskingum method. The algorithm is designed to achieve enhanced fixed-size parallel speedup and uses a mathematical approximation applied at the boundaries of large subbasins. In order to use such an algorithm, a balanced domain decomposition method that differs from the traditional classifications of river reaches and subbasins and based on network topology is developed. An application of the algorithm and domain decomposition method to the Mississippi River Basin results in an eightfold decrease in computing time with 16 computing cores which is unprecedented for Muskingum-type algorithms applied in classic parallel-computing paradigms having a one-to-one relationship between cores and subbasins. An estimated 300 km between upstream and downstream reaches of subbasins guarantees the applicability of the algorithm in our study and motivates further investigation of domain decomposition methods.