Heuermann pleaded not guilty and maintained his innocence.
Heuermann was previously considered a top suspect in the case but at the time of his arrest, investigators said they did not have the evidence to charge him with her death.
The Gilgo Beach task force has been investigating the deaths of 10 people whose remains were found along the New York beach in 2010 and 2011. Most of the victims were sex workers.
In July, police arrested 60-year-old Heuermann for the murders of three women, with police considering him as a suspect in the death of a fourth. Police used familial DNA evidence to help identify Heuermann.
At the time, he was charged with the deaths of Melissa Barthelemy, 24, Megan Waterman, 22, and Amber Lynn Costello, 27. They, along with Brainard-Barnes, were known as the Gilgo Four.
All four women were sex workers; Barthelemy’s family said a man using her phone had taunted the family with graphic details of what he had done to her sexually and said he killed her.
Heuermann was taken into custody and is being held in a Suffolk County correctional facility awaiting trial.
In court filings Tuesday, prosecutors allege Heuermann feared getting caught in the months leading up to his arrest.
He obtained data wiping software in an attempt to destroy evidence on his laptops, phones and other electronic devices, they said. Investigators seized hundreds of devices during their lengthy search of Heuermann’s home that prosecutors say contained troves of bondage and torture pornography.
Heuermann also scoured the internet for phrases that suggested he was afraid of getting caught, including “How does cell site analysis work,” “Gilgo news,” “How cell phone tracking is increasingly being used to solve crimes,” and phrases with the term “Long Island Serial Killer.”
The court documents also detail disturbing Google searches Heuermann was allegedly conducting, such as “autopsy photos female,” “medieval torture of women” and “how I was raped audio.” He also made searches for pornographic material of women tied up.
Heuermann’s attorney, Michael Brown, said afterward that his client has maintained his innocence from “day one” and looked forward to defending himself in court.
FILE PHOTO: Maureen Brainard-Barnes (top L), Melissa Barthelemy (top R), Megan Waterman (bottom L) and Amber Lynn Costello (bottom R) are seen in a combination of handouts released to Reuters by Suffolk County Police Department April 6, 2011. Four bodies found dumped on a remote Long Island beach were officially identified as prostitutes who were likely slain by a serial killer, police said. The women were killed at another location and their bodies were transported to Gilgo Beach, about 64 km (40 miles) east of New York City, Suffolk county, New York police said. The bodies were discovered in early December. “All of the women were escorts, who were self-employed and used Craig’s List and other sites to arrange meetings with clients,” said a police spokesperson, reading from a statement issued by Police Commissioner Richard Dormer. REUTERS/Suffolk County Police Department/Handout (UNITED STATES – Tags: CRIME LAW SOCIETY) FOR EDITORIAL USE ONLY. NOT FOR SALE FOR MARKETING OR ADVERTISING CAMPAIGNS/File Photo
FILE – Crime scene investigators use metal detectors to search a marsh for the remains of Shannan Gilbert, Dec. 12, 2011 in Oak Beach, New York. A Long Island architect has been charged, Friday, July 14, 2023, with murder in the deaths of three of the 11 victims in a long-unsolved string of killings known as the Gilgo Beach murders. (James Carbone/Newsday via AP, Pool, File)
WANTAGH, NY – APRIL 15: An aerial view of police cars near where a body was discovered in the area near Gilgo Beach and Ocean Parkway on Long Island on April 15, 2011 in Wantagh, New York. Police have been conducting a prolonged search of the area after finding ten sets of human remains. Of the ten only four sets of remains have been identified as missing female prostitutes in their 20s who had been working in the online escort business. Police, working with the Federal Bureau of Investigation (FBI), suspect that a single serial killer may be in the New York area focusing on sex workers. (Photo by Spencer Platt/Getty Images)
Authorities search the home of suspect Rex Heuermann, Tuesday, July 18, 2023, in Massapequa Park, N.Y. Detectives investigating the long-unsolved slayings known as the Gilgo Beach killings have continued their searches, recently including a storage facility in the Long Island community of Amityville over the weekend. (AP Photo/John Minchillo)
Authorities search the home of suspect Rex Heuermann, Tuesday, July 18, 2023, in Massapequa Park, N.Y. Detectives investigating the long-unsolved slayings known as the Gilgo Beach killings have continued their searches, recently including a storage facility in the Long Island community of Amityville over the weekend. (AP Photo/John Minchillo)
Authorities search the home of suspect Rex Heuermann, Tuesday, July 18, 2023, in Massapequa Park, N.Y. Detectives investigating the long-unsolved slayings known as the Gilgo Beach killings have continued their searches, recently including a storage facility in the Long Island community of Amityville over the weekend. (AP Photo/John Minchillo)
A crime laboratory officer removes a box of items as law enforcement searches the home of Rex Heuermann, Saturday, July 15, 2023, in Massapequa Park, N.Y. Heuermann, a Long Island architect, was charged Friday, July 14, with murder in the deaths of three of the 11 victims in a long-unsolved string of killings known as the Gilgo Beach murders. (AP Photo/Jeenah Moon)
The family of accused Gilgo Beach serial killer may seek damages after a search of their home. (Asa Ellerup via Robert Macedonio)
Suffolk County District Attorney Raymond Tierney speaks at a news conference to announce the identity of a victim investigators had called the “Jane Doe No. 7,” as Karen Vergata, Friday, Aug. 4, 2023, in Hauppauge, New York. Law enforcement authorities said Friday they have identified a woman whose remains were found as far back as 1996 in different spots along the Long Island coast, some of them near the Gilgo Beach locations of bodies investigators believe were left by a serial killer. (AP Photo/John Minchillo)
Accused Gilgo Beach killer Rex A. Heuermann appears before Judge Timothy P. Mazzei in Suffolk County Court on Tuesday, August 1, 2023.
He also called into question some of the evidence touted by prosecutors Tuesday, suggesting new DNA analysis connecting Heuermann to the killing was “problematic” since it was being introduced some 13 years after Brainard-Barnes’ body was discovered.
Suffolk County District Attorney Raymond Tierney said in response that more sophisticated DNA testing had allowed investigators to more conclusively determine the hairs found with Brainard-Barnes belonged to Heuermann’s ex-wife and daughter.
He also said the indictment marks the end of the investigation into the so-called “Gilgo four” victims and provides “some small measure of closure” for their families.