Bana was born in Melbourne, Victoria. His father, Ivan, was Croatian and worked as a logistics manager for Caterpillar, Inc., and his German mother, Eleanor, was a hairdresser, originally from near Mannheim in Germany. He has one older brother, Anthony. Bana grew up in Melbourne's Tullamarine, a suburban area on the northern edge of the city, near Melbourne's international airport, and attended Penleigh and Essendon Grammar School. In a cover story for The Mail on Sunday, he told author Antonella Gambotto-Burke that his family had suffered from racist taunts, and that it had distressed him. "Wog is such a terrible word," he said. He has stated: "I have always been proud of my origin, which had a big influence on my upbringing. I have always been in the company of people of European origin".
Showing acting skill early in life, Bana began doing impressions of family members at the age of six or seven, first mimicking his grandfather's walk, voice and mannerisms. In school, he mimicked his teachers as a means to get out of trouble. As a teen, he watched the Mel Gibson film Mad Max (1979), and decided he wanted to become an actor. However, he did not seriously consider a career in the performing arts until 1991 when he was persuaded to try comedy while working as a barman at Melbourne's Castle Hotel. His stand-up gigs in inner-city pubs did not provide him with enough income to support himself, however, so he continued his work as a barman and waiting tables.