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.David Crosby, interviewed for the documentary Joni Mitchell: Woman of Heart and Mind, stated that Mitchell had captured the feeling and importance of the Woodstock festival better than anyone who had been there.
The lyrics tell a story about a spiritual journey to Max Yasgur's farm, the place of the festival, and makes 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 the Vietnam War ("bombers flying shotgun in the sky").
About the same time that Ladies of the Canyon appeared, Crosby, Stills, Nash & Young's upbeat hard rock arrangement was released as lead single from their Déjà Vu album. This version opens with a distinct lead guitar lick played by Stephen Stills who sings the lead vocal with backing harmonies from David Crosby and Graham Nash. The Crosby, Stills, Nash & Young version of "Woodstock" is also notable for the start-stop patterns just prior to the "We are stardust, we are golden..." chorus. 
Although Crosby, Stills, Nash & Young learned the song from Joni Mitchell herself, the band's version slightly rearranged the lyrics from her original. They put the line, "we are billion year old carbon"—which only appeared in her final chorus—into each of the first three choruses. Then they replaced that line with "we are caught in the devil's bargain" in the last chorus which was also in Mitchel's final chorus.
"Woodstock" was one of the few Déjà Vu tracks where Crosby, Stills, Nash & Young all performed their parts in the same session. Later the original lead vocal by was partly replaced with a vocal recorded by Stills who recalled: "I replaced one and a half verses that were excruciatingly out of tune." Neil Young disagreed, saying "the track was magic. Then later on [Crosby, Stills & Nash] were in the studio nitpicking [with the result that] Stephen erased the vocal and put another one on that wasn't nearly as good." The Crosby, Stills, Nash & Young version of "Woodstock" peaked at #11 on the Billboard Hot 100 in May 1970. A different recording of "Woodstock" by Crosby, Stills, Nash & Young was played under the closing credits of the documentary film Woodstock released March 1970.
"Woodstock" became an international hit in 1970–71 via a version by Matthews Southern Comfort whose frontman Iain Matthews recalled, "We had to do four songs on a BBC [Radio] lunchtime show. We worked up an arrangement for 'Woodstock'" – which Matthews knew from Mitchell's Ladies of the Canyon album – "and the response was so good that we [recorded and released it] as a single."
Andy Leigh, the group's bassist, said, "We took [the song] apart and reassembled it and we knew we had something. We were an album band. We didn't do singles. But we knew this...was something special...The record company said they would only release [our version] if [Crosby, Stills, Nash & Young] did not have a [UK] hit with theirs". After the CSN&Y version failed to reach the UK charts "[MCA] reluctantly released ours because of that agreement but they wouldn't spend a penny on promotion...But our managers, who were excellent, hired a PR, a songplugger. Tony Blackburn, who had the breakfast show on Radio 1, played 'Woodstock' and kept playing it and other DJs started doing the same." 
Issued 24 July 1970, "Woodstock" debuted on the UK Top 50 on 26 September 1970 and reached #1 on 31 October 1970 remaining there for two additional weeks. It also afforded Matthews' Southern Comfort an international hit, charting in Austria (#15), Germany (#27), Finland (#23), Ireland (#2), the Netherlands (#17), Norway (#2), Poland (#2), Sweden (#2), South Africa (#3) and the US (#23).
America remade "Woodstock" for their 2012 release Back Pages a cover album that according to group member Gerry Beckley comprises "killer songs that are great examples that come from our best songwriters." Beckley's co-member Dewey Bunnell states: "Joni Mitchell's 'Woodstock' is an anthem for me in the truest sense...a call to action....and I've always been a child of the 60's at heart."
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.
In an episode of the television drama The West Wing, "The Warfare of Genghis Khan", a NASA administrator 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'".
The 20th episode of Six Feet Under, "Back to the Garden", takes its title from the song's lyrics, and features it prominently in the episode, including a closing scene in which Frances Conroy, in a broken voice, sings along with the song as it plays from a cassette tape.
British punk group Chumbawamba referenced a lyric in their song "I'm Not Sorry, I Was Having Fun." The lyric "By the time we got to Woodstock, we were half a million strong" became "By the time I got to Woodstock, it was going up in flames," referring to the disastrous Woodstock 1999 festival.