We show that the asymptotic symmetries of higher-spin gauge theories coupled to 3D gravity with a negative cosmological constant correspond to non-linear W-algebras. To this end, we first present a description of these couplings in terms of G x G Chern-Simons actions. Then we identify the asymptotically AdS solutions of the field equations and we show that their asymptotic symmetries are given by two copies of a centrally extended W-algebra selected by the gauge group G. The central charge is the one identified by Brown and Henneaux in pure gravity.