Charles Mundine attended Catholic primary and high schools in the Grafton area in New South Wales before at age thirteen his family moved to Sydney, where he attained his School Certificate at Benedict Marist Brothers in Auburn. He then completed an apprenticeship as a technician with PMG.
In the early 1970's, Mundine joined the Army. The Vietnam War was ending and so he worked on army electronics for more than twenty-one years. After a long career in the Army, Mundine left the Armed Services and began working for the New South Wales Corrective Service as a drug and alcohol counsellor. It was at this critical point that he realised the benefits of talking and working with young people and the necessity of discussing socially sensitive subjects such as family and domestic violence and sexual health.
Charles Mundine worked for Link-Up New South Wales, an Aboriginal Corporation which was founded around 1980 to assist all Aboriginal people who have been fostered, adopted or raised in institutions to find their way home. Link-Up also assists young people who are, or have been, in jeopardy of being removed from their family.