King was born on Norfolk Island. He was the son of Anna Josepha ("née" Coombe) and Philip Gidley King. He was named after his father's mentor, Arthur Phillip, the first governor of New South Wales and founder of the British penal colony which later became the city of Sydney. This explains the difference in spelling of his and his father's first names.