We show that the four-dimensional Chern-Simons theory studied by Costello, Witten and Yamazaki, is, with Nahm pole-type boundary conditions, dual to a boundary theory that is a three-dimensional analogue of Toda theory with a novel 3d W-algebra symmetry. By embedding four-dimensional Chern-Simons theory in a partial twist of the five-dimensional maximally supersymmetric Yang-Mills theory on a manifold with corners, we argue that this three-dimensional Toda theory is dual to a two-dimensional topological sigma model with A-branes on the moduli space of solutions to the Bogomolny equations. This furnishes a novel 3d-2d correspondence, which, among other mathematical implications, also reveals that modules of the 3d W-algebra are modules for the quantized algebra of certain holomorphic functions on the Bogomolny moduli space.