Mr Karjalainen held the top ANZ position on an interim basis prior to Mr Gillenwater's appointment.
Mr Gillenwater said "There is a fantastic opportunity for BlackBerry in Australia and New Zealand's thriving smartphone market. I look forward to working with our partners and talented internal teams to focus on our business strategy with an immediate emphasis on preparing for the highly anticipated BlackBerry 10 launch."
He has held various positions at RIM in North America and in South East Asia, and has also held sales positions at Verizon Wireless.
Mr Gillenwater's predecessor, longtime RIM employee Adele Beachley, left the company in February "to pursue other interests". At the time, the Australian Financial Review reported that when it asked Ms Beachley to comment it was threatened with legal action by her lawyers, and that legal action was being taken against an unspecified online publication for "unattributed allegations about the circumstances of her departure."