Narodil sa 5. októbra 1957 vo veľmi umelecky živej časti New Yorku v Harleme. Anderson vyrastal obklopený hudbou, jeho otec bol organista a mama speváčka a klaviristka. Na trombóne začal hrať v siedmich rokoch, keď mu nástroj kúpil práve jeho strýko – Sonny Rollins. Svoje hudobné štúdium začal...