Following his first-class debut in the Logan Cup in April 2008, he was called up to the national team for a tour of Bangladesh, where he made his international debut in a One Day International on 19 January 2009. Chasing mere 128, Zimbabwe were in trouble at 44/6 when Waller walked in and drove his first ball through the covers for four. He played a few more encouraging shots and was the top scorer in the innings with 24. With Ray Price's entertaining shots in the end Zimbabwe won by 2 wickets eventually.
Malcolm Waller rose to fame when he helped Zimbabwe to chase down their highest ever target in One Day International of 328 against New Zealand at Bulawayo in the third ODI. He showed immense character to chase a total of more than 300 for the first time in Zimbabwe's history by remaining unbeaten on 99.
Following this, he made his Test debut against New Zealand in the only Test at Bulawayo on 1 November 2011. Waller remained unbeaten on 72 and became the eleventh Zimbabwean to score 50 or above in his debut test.
Waller's father, Andy, played for Zimbabwe in the 1980s and 1990s. His father also scored 50 in his debut Test albeit in the second innings. His cousin, Nathan Waller also represented Zimbabwe under-19 teams.