1960年5月25日(マイルスの誕生日の前日）、フィラデルフィア生まれ。
ミュージシャン兼ボクサーだった父親から5歳の時トランペットを与えれ、その2年後には本格的なレッスンを開始する。1972年にはPhiladelphia Settlement Music Schoolでクラシックのブラスアンサンブルに参加した。家族がワシントンへ引っ越した時、エリントン高校に入学。ミッキー・ベースの指導を受け、ハワード大学に1年間在籍した後バークリー音楽大学に編入。在学中にはアブドゥル・イブラヒムのヨーロッパツアーに参加したり、1980年夏にはジャズ・メッセンジャーズ・ビッグバンドに参加、翌81年後半にも一時的にジャズ・メッセンジャーズで演奏した。以降チコ・フリーマン、リッキー・フォード、ビリー・ハーパーらと共演し、1986年春から約1年間ジャズ・メッセンジャーズの正式メンバーとして活動。同年11月からは故トニー・ウィリアムス・クインテットにも参加し数多くの名盤を産み出した。
若い頃からマイルス・デイビスに心酔。1987年にはミューズレコードより待望の初リーダー作「ヴァーセス」を発表。60年代マイルス・クインテットの音楽性を継承したフレッシュなサウンドで一躍注目を集めた。マイルスの晩年（1991年）にはモントルー・ジャズ・フェスティバルにおいてマイルスのサポート役も担いマイルス本人から賛辞を受ける。
1992年にハービー・ハンコックが行ったマイルスへのトリビュート・ツアーにも抜擢され、ウェイン・ショーター、ロン・カーター、トニーらに交じり素晴らしい演奏を聴かせポスト・マイルスの座を不動のものとする。
リーダー作は今日まで12作品を数える。9作目の「ミステリオス」より（マイルスが最期に所属していた）ワーナー・ブラザーズに移籍。またサイドメンとしても多くの録音に参加。若手〜中堅トランペッターとしてはウィントン・マルサリスと並び別格的存在である。
マイルスの遺言で愛用のトランペットを贈られたウォレスはその意志を継ぎ、マイルスと同じく孤高の存在まで登り詰めつつある。