Paul Behrendt was born into a family of nine children and his mother died not long after his younger brother's birth. Behrendt's father was unable to support the children, and the children were sent to Burnside Home in Sydney. At the age of twelve Paul Behrendt returned to live with his father and stepmother.
Behrendt returned to his ancestral lands and made contact with family members, including his mother's cousin, although his mother had died.
Behrendt worked as Aboriginal Fellow in the Faculty of Liberal Studies at the University of New South Wales.