The Wiener filter has emerged as a standard tool for the inference of high dimensional signals, such as the large scale structures and cosmic microwave background (CMB) problems. Some particularly key applications of the Wiener filter in CMB data analysis include power spectrum estimation, map-making and the reconstruction of lensing potential. We present a new fast and robust iterative solver, via a formulation that is dual to the recently developed messenger technique, to efficiently calculate the Wiener filter solution of large and complex data sets. Like its predecessor, this new dual messenger algorithm does not require an ingenious choice of preconditioner and can account for inhomogeneous noise distributions and arbitrary mask geometries, while being unconditionally stable. We demonstrate the capabilities of this hierarchical scheme in signal reconstruction by applying it on a simulated CMB temperature data set to investigate the effectiveness of reconstruction and convergence properties. The dual messenger algorithm outperforms the standard messenger and the popular preconditioned conjugate gradient (PCG) schemes in terms of execution time, being roughly a factor of 2 and 4 times faster than the respective methods, for the specific problem considered. We also showcase the application of the dual messenger algorithm on polarised CMB data sets, where traditional techniques such as the PCG run into numerical difficulties due to the significant increase in the condition number of the matrices involved. This new high-performance algorithm is particularly adapted to cope with the complex numerical challenges posed by state-of-the-art data sets and is therefore relevant for current and future high-resolution CMB missions such as Planck, South Pole Telescope, Advanced ACTPol, Simons Observatory and CMB S-4.