But the Birnie household was far from normal. David Birnie's sexual appetite was seemingly insatiable. James Birnie, David's younger brother, stayed with the couple for a short time when he was released from prison after serving five months for indecently interfering with his six-year-old niece. He told a reporter: '(The six-year-old) led me on. You don't know what they can be like. When I left prison, I had nowhere to go. I couldn't go back to my mother's place because I had assaulted her and there was a restraining order out against me. I had a couple of fights with mum and the police chased me off. Mum has alcohol problems. So David and Catherine let me move in. They weren't real happy about it and David kept saying that he was going to kill me to keep me in line.'
James added that David Birnie had few friends, was heavily into kinky sex and had a big pornographic video collection. "He has to have sex four or five times a day," James said of his brother. "I saw him use a hypodermic of that stuff you have when they're going to put stitches in your leg. It makes you numb. He put the needle in his penis. Then he had sex. David has had many women. He always has someone."
The killings started in 1986. David and Catherine Birnie had tried everything sexually together and they wanted new kicks. They discussed abduction and rape. Birnie turned his accomplice on by telling her that she would achieve incredible orgasms by watching him penetrate another woman who was bound and gagged. Catherine believed him.
Their first opportunity came on 6 October 1986 when 22-year-old student, Mary Neilson, turned up at the Birnie house to buy some car tyres. She had approached Birnie at his work at the spare parts yard and he had suggested that she call by his house for a better bargain.
Mary was studying psychology at the University of Western Australia and worked part time at a suburban delicatessen. She was hoping to take a job as a counsellor with the Community Welfare Department. Her parents were both TAFE lecturers and were in the UK on holiday when their daughter disappeared.
Mary was last seen leaving the shop on Monday 6 October to attend a University lecture. But she never made it. Her Galant sedan was found six days later left in a riverside car park opposite police headquarters. David Birnie had driven it there. It was as if he was leaving a clue.
As Mary Neilson entered the Birnie house she was seized at knife point, bound and gagged and chained to the bed. Catherine Birnie watched as her lover repeatedly raped the girl. She asked him questions about what turned him on the most. This way she would know what to do to excite him.
Catherine knew that Mary Neilson would eventually have to die. But it was something that she and Birnie hadn't yet discussed. That night they took the girl to the Gleneagles National Park where Birnie raped her again then wrapped a nylon cord around her neck and slowly tightened it with a tree branch.
Mary Neilson choked to death at his feet. Birnie then stabbed her through the body and buried her in a shallow grave. He told Catherine that the stab wound would allow any gases to escape as the body decomposed. He had read it somewhere in a book.