Mailman grew up in Mount Isa in north-west Queensland. She is one of five children born to Wally Mailman, a famous rodeo rider and horseman, and Jane (Heeni) Mailman, the daughter of a preacher and talented musician. She has both Indigenous Australian (Bidjara) and Māori (Ngati Porou and Te Arawa) heritage. In 1992, she graduated from Queensland University of Technology Academy of the Arts with a Bachelor of Arts majoring in Performing Arts. Since then she has worked extensively in Australian film, television and theater as well as many contributions overseas. She played the role of Kate in a La Boite Theatre production of Shakespeare's The Taming of the Shrew in 1994.
Mailman was featured prominently in the Leah Purcell documentary Black Chicks Talking (2001), where she candidly discussed her thoughts about her Aboriginal heritage. In 2006, she took part in a four-part television documentary series with Cathy Freeman called Going Bush, where the pair set off on a journey from Broome to Arnhem Land spending time with Indigenous communities along the way.