As soon as it was light Gerry and I resumed our search. We jumped over walls and raked through undergrowth. We looked in ditches and holes.
The most striking thing was we were completely alone. Nobody else, it seemed, was out looking for Madeleine.
There didn't seem to be much sense of urgency.
According to the Polícia Judiciária files, two patrol dogs were brought to Praia da Luz at 2am on May 4 and four search-and-rescue dogs at 8am. The tracker dogs did not go out until 11pm.
There had been no house-to-house inquiries.
It was about 10am by the time a couple of PJ officers turned up to take us and our friends to the police station in Portimão.
I was appalled by the treatment we received. Officers walked past us as if we weren't there. Nobody asked whether we were OK. Our child had been stolen and I felt as if I didn't exist.
It was gone 2pm at the police station in Portimão before I was interviewed.
As João Carlos, a Portuguese detective, led me up the stairs, I inquired whether he had any children. He told me he hadn't. "But don't worry. We will find your daughter." It was exactly what I was yearning to hear.
It was 7.30 by the time one of the PJ officers drove us away from the police station. Ten or 15 minutes into our journey, the police officer had a call from his station. He suddenly swung the car into a U-turn and drove us at 120mph back to Portimão.
Anguish ... Kate, with Cuddle Cat, and Gerry in tearful appeal for help days after disappearance
Had Madeleine been found? Was she alive? Was she dead? I was crying hysterically and praying for all I was worth.
Back at the police station somebody showed us a photograph from CCTV of a blonde child with a woman in a petrol station shop. We were asked whether the little girl was Madeleine. She wasn't. We were sent on our way, devastated.
Four months later, doctors Kate, 43, and Gerry, 42, were still in Portugal. She recalls with horror how she learned police had made them the main suspects.
On August 2 I had a call from Gerry. The police wanted to come over at 10am. Something to do with forensics.
It was 5pm when they eventually showed up. They told us they wanted to shoot some video footage of our clothes and possessions.
The forensics people would then take these away and return them the following day.
They offered no explanation. We were all asked to leave the villa. When we were allowed back, I was devastated. They had taken my Bible, Cuddle Cat (Madeleine's favourite toy) and my diaries.
It was on Monday August 6 that the atmosphere changed.
At the Polícia Judiciária's request, Gerry went to meet them at a café in Portimão. He returned minus the car. The police had impounded it for forensic testing.
Madeleine had been missing for over three weeks when we'd hired the car, but perhaps it still needed to be ruled out of the investigation. That lunchtime I was ambushed by journalists and TV cameras.
It emerged that there had been stories in some Portuguese papers suggesting Gerry was somehow involved in Madeleine's disappearance.
Sniffer dogs had discovered traces of Madeleine's blood in apartment 5A, it was claimed.
It was insinuated she died there and her body had been dumped in the sea. The following day it was reported a sample of "blood" had been sent to the UK to see whether a DNA profile could be extracted from it.
We had seen no blood that night - neither, as far as we knew, had any been found by the police or the forensics team from Lisbon.
Two days later, Kate and Gerry went to the police station to meet investigator Luís Neves and Guilhermino Encarnação, director of the Algarve Polícia Judiciária. It quickly became clear they were focussing on the McCanns, Kate recalls.
There had been a shift in the investigation, they said. Tell us about that night, they said. Tell us everything that happened after the children went to bed. I gave them every detail I could remember, as I had before.
Neves stated bluntly they didn't believe my version of events. It "didn't fit" with what they knew.
Didn't fit? What did they know? They proposed that when I'd put Madeleine to bed that night, it wasn't actually the last time I'd seen her. But it was. It was! I was being bullied. I assume these tactics were deliberate - knock her off balance by telling her that her daughter is dead and get her to confess.
On and on it went. Then it was Gerry's turn. Through his tears he pleaded with the two men: "Do you have evidence that Madeleine is dead? We're her parents. You have to tell us."
"It's coming," Neves told him.
Our liaison officer Ricardo Paiva arrived. He told us about two springer spaniels brought out to Portugal by the British police to assist in the search.
Keela, who could alert her handler to the tiniest trace of blood, had done so in apartment 5A. Eddie, a dog trained to detect human remains, had indicated somebody had died there.
The police appeared to be telling us, on the say-so of a dog, that someone had definitely died in apartment 5A and it must have been Madeleine.
On Thursday September 6, Kate was interviewed at Portimão police station in the presence of her lawyer, Carlos Pinto de Abreu. Within hours both she and Gerry would officially be classed as arguido, or suspects.
There were three PJ officers in the room. João Carlos asked most of the questions, which I answered in as much detail as I could. Back at the apartment later that night my lawyer Carlos reiterated that the situation was not good. The PJ had a lot of "evidence" and I was certain to be made an arguida in the morning.
First he cited video footage the police had shot of the reactions of the blood and cadaver dogs in apartment 5A and also around our hire car.
I was totally perplexed. If, as the PJ alleged, Madeleine's blood was in the boot of our car, which we had not rented until May 27, how on earth had it got there? Did this mean someone had planted it? I could see no other explanation.
The police theory, it seemed, was that we had hidden Madeleine's body, then moved it later and buried it elsewhere.
A witness claimed to have seen Gerry and me carrying a big black bag and acting suspiciously. This was absolute nonsense.
Friday 7 September. After a measly two hours' sleep we got up and braced ourselves for the day ahead.
The street leading to the police station was again lined by huge crowds of press and onlookers.
Carlos had advised me not to answer any of the questions put to me. He explained that this was my right as an arguida and the safest option. Any responses I gave might unintentionally implicate me in some way.
Book ... out May 12
Then they started. What had I seen and heard after entering apartment 5A at 10pm on 3 May 2007? Who called the police? At what time? Who contacted the media?
Ricardo Paiva played a more prominent role in the interrogation this time, giving me his spiel about the dogs. "These dogs have a 100 per cent success rate," he said.
"Two hundred cases and they've never failed." I just stared at him, unable to hide my contempt. These dogs had never been used in Portugal before, and he knew little more about them than I did.
Ricardo started a video player. I saw the dogs going into apartment 5A, one at a time, with the handler.
Each dog ran around the apartment, jumping over beds, into the wardrobe, generally having a good sniff.
At one point, the handler directed the dogs to a spot behind the couch in the sitting room, close to the curtains. He called the dogs over to him to investigate this site.
This was not what I'd call an exact science.
The film show continued. Now we were in an underground garage where eight or so cars were parked, including our rented Renault Scenic.
It was hard to miss. The windows were plastered with pictures of Madeleine. One of the dogs ran straight past our car, nose in the air, heading towards the next vehicle.
The handler stopped next to the Renault and called the dog. It obeyed, returning to him, but then ran off again. The handler instructed the dog to come back several times and directed it to certain parts of the vehicle before it eventually supplied an alert by barking.
Each time a dog gave a signal, Ricardo would pause the video and inform me blood had been found in this site and that the DNA from the sample matched Madeleine's.
He would stare at me intently and ask me to explain this. These were the only times I didn't respond with a "No comment."
Instead I said I couldn't explain it, but neither could he.
When researching sniffer-dog evidence later, Gerry would discover false alerts can be attributable to the conscious or unconscious signals of the handler. We would later learn that in his written report, the handler emphasized such alerts cannot be relied upon without corroborating evidence.
As I walked out of the interview room at 3.15pm, Gerry was on his way to Portimão for his interrogation. Like me, he was officially declared an arguido at the start of the proceedings.