McKenzie's modeling career first gained traction in Paris, France. She modeled for top designers including Jean Paul Gaultier, Thierry Mugler and Christian Lacroix.
She was commissioned to work in markets around the globe following her initial success in Paris, and worked in London, Italy, Austria, the United States and Japan, working for Alexander McQueen, Betsey Johnson, Tommy Hilfiger, Todd Oldham and Michiko Koshino. Her magazine covers include Essence, Le Monde and Panache, as well as editorials in Vogue (US, Japan, Korea, Britain, Spain), Harper's Bazaar, Interview, Flare, Fashion, and Vibe.
McKenzie was a main judge on the first season of Canada's Next Top Model in 2006, later serving as a guest mentor on two episodes of cycle 23 of America's Next Top Model in 2017, and becoming the runway pack of cycle 24 in 2018.
She made her acting debut in the 1996 film Portraits Chinois but gained more attention in the 1997 film The Fifth Element as a VIP Stewardess.