It continues a long battle over how much information about the incident ought to be made public.
The video shows the Columbine gunmen chuckling as they fire four different weapons, including automatic rifles, shotguns and a pistol, at trees and bowling pins.
The video, taken on a shaky handheld camera on a snow-covered hillside in a national forest south of Denver, is the first made by the gunmen themselves to be released to the public.
Among other scenes, the video shows a smiling Harris blowing across the upturned muzzle of a shotgun like a gunslinger. Both teens wear trench coats, and later show the camera hands made bloody by a gun butt.
"Guns are bad. When you saw them off and make them illegal, bad things happen to you," one says. The two then point at a gun and mockingly spank it as Klebold says, "no, no, no."
Parents of some of the victims actually urged authorities to release the video, reports CBS News Correspondent Bill Whitaker.
"There's just been an attempt to hide all kinds of information," said Brian Rohrbough, whose son Danny was killed in the Columbine massacre. "It maybe uncomfortable to watch. Certainly I wouldn't let my kids watch it, but it's something that is important in understanding Columbine and trying to prevent another school shooting."
For others, including those Connie Michalik, it's reopening old wounds. Her son Richard was paralyzed in the shooting.
"It upsets me that we're giving these kids notoriety," Michalik said. "It just hurts. They're out there practicing these horrible weapons and we're here at home, innocently not knowing anything and there's people out there that should have been protecting these children and my son and they weren't."
"It hurts a lot because basically they're practicing killing people. And it's painful to know that in their mind that their motive and intent was April 20th, so it's hard to know that they were so deliberate in their actions," Beth Mimmo, whose daughter Rachel Scott was killed in the attack and whose son Craig survived, told the CBS News Early Show.
Four-and-a-half years after the country's most deadly school shooting, much information remains under seal or in official hands. Many believe that material might shed more light on the incident.
"I agree that we definitely need to release some of this stuff so that other people can, you know, so that we can learn some of the lessons from Columbine and hopefully stop another massacre like this ever happening again," said Beth's stepfather, Larry Mimmo.
But it was unclear what insights the tape might provide. Essentially, it is film of teenagers firing weapons in the woods — not an uncommon activity. What was unusual was the conversations among the young men, including talk of entry and exit wounds.
"They apparently did say the discussion about hitting a bowling pin and what would that be like against somebody's head. I guess that should be a flag for somebody," said Larry Mimmo. The lesson, said Mimmo, was: "Heed the warning signs."
"Eric and Dylan didn't just create this thing overnight," he said. "This took months and months and months of planning and talking. But if people see a warning sign I mean, then something needs to happen."
The Jefferson County sheriff's office long ago released surveillance video showing the suicidal teenagers as they entered the Columbine High School cafeteria during the attack.
The latest video was released as part of an ongoing effort by the sheriff's office and a task force established by the attorney general to examine evidence assembled during the Columbine investigation. The goal is to release as much evidence as possible to the public.
The video also shows Mark Manes shooting some of the weapons. Manes sold Harris and Klebold a TEC-DC9 semiautomatic handgun for $500 about three months before the massacre. The gun was used in the attack.
Manes pleaded guilty to providing a handgun to minors and possessing an illegally sawed-off shotgun and was sentenced in 1999 to six years in prison. He was released to a halfway house after less than two years.
The man who taped the target practice was Philip Duran, who worked with Harris and Klebold at a pizza shop, Jefferson County district attorney's spokeswoman Pam Russell said.
Duran, who was accused of introducing Harris and Klebold to Manes, was charged with providing a gun — the TEC-DC9 — to a minor and possessing a dangerous or illegal weapon, a sawed-off shotgun. He was sentenced in June 2000 to 4½ years in prison.
In a videotaped message before the attack, the gunmen thanked Manes for providing the gun, saying they couldn't have done it without his help. They also warned him that he and Duran would probably be blamed for helping with the assault.
Lawsuits to release the so-called "basement video tapes" — made by Harris and Klebold in the months before the attack — are pending. The sheriff's office has allowed reporters to watch the tapes, but has not released copies to the public.