Many problems in stellar astrophysics feature flows at low Mach numbers. Conventional compressible hydrodynamics schemes frequently used in the field have been developed for the transonic regime and exhibit excessive numerical dissipation for these flows. While schemes were proposed that solve hydrodynamics strictly in the low Mach regime and thus restrict their applicability, we aim at developing a scheme that correctly operates in a wide range of Mach numbers. Based on an analysis of the asymptotic behavior of the Euler equations in the low Mach limit we propose a novel scheme that is able to maintain a low Mach number flow setup while retaining all effects of compressibility. This is achieved by a suitable modification of the well-known Roe solver. Numerical tests demonstrate the capability of this new scheme to reproduce slow flow structures even in moderate numerical resolution. Our scheme provides a promising approach to a consistent multidimensional hydrodynamical treatment of astrophysical low Mach number problems such as convection, instabilities, and mixing in stellar evolution.