Joni Mitchell wrote the song from what she had heard from then-boyfriend, Graham Nash, about the Woodstock Music and Art Festival. She had not been there herself, since she was told by a manager that it would be more advantageous for her to appear on The Dick Cavett Show. She wrote it in a hotel room in New York City, watching televised reports of the festival. "The deprivation of not being able to go provided me with an intense angle on Woodstock," she told an interviewer shortly after the event.
Lyrics tell a story about a spiritual journey to the Max Yasgur's farm, the place of festival, and making prominent use of religious imagery, comparing the festival place with the Garden of Eden ("...and we've got to get ourselves back to the garden"). The saga commences with the narrator's encounter of a fellow traveler ("Well, I came upon a child of God, he was walking along the road") and concludes at their ultimate destination ("by the time we got to Woodstock, we were half a million strong..."). There are also references to Vietnam War ("bomber death planes flying shotgun in the sky"). 
Mitchell's original version featured a stark and haunting arrangement - solo vocal, multi-tracked backing vocals and tremoloedWurlitzer electric piano, all performed by Mitchell herself. All subsequent recordings featured a fuller backing band sound.
Prior to release on any album, Mitchell performed "Woodstock" at the 1969 Big Sur Folk Festival, one month after Woodstock. The solo performance can be seen in the festival concert film Celebration at Big Sur (released in 1971). The performance was an exception to Mitchell's mounting distaste for large festival gigs.
Crosby, Stills, Nash & Young's upbeat hard rock arrangement of the song is one of the most well known version of the song, arguably overshadowing the original one, has reached #11 on the Billboard Hot 100. This version opens with a distinct, memorable lead guitar lick played by Stephen Stills. Stills also sings lead vocals in addition with backing harmonies from David Crosby and Graham Nash. This arrangement is also notable for the start-stop patterns just prior to the "We are stardust, we are golden..." chorus.
The Assembled Multitude's 1970 instrumental version reached #79 in the US. David Crosby, in an interview in the documentary Joni Mitchell: Woman of Heart and Mind, said that Mitchell had captured the feeling and importance of the Woodstock festival better than anyone who had been there.
A line from the chorus, "We are billion year old carbon," was used by Corey Mesler as the title of a novel about the 1960s.
American rapper Astronautalis quoted the previous part of the chorus in his song "Dimitri Mendeleev": "Joni Mitchell said 'We are stardust, we are golden'".
In an episode of the fictional US political television drama, The West Wing, "The Warfare of Genghis Khan" (Series 5, Episode 13), a NASA Assistant Administrator, Alex Moreau, shows the Orion Nebula to Josh Lyman through a telescope and describes it to him, explaining that "Everything, every atom in our bodies, comes from exploding stars" and concluding "I guess Joni Mitchell was right: 'We are stardust'".