The song came together on the day that John Fogerty got his discharge papers from the US Army. Fogerty had been drafted in 1966 and was part of a Reserve unit, serving at Fort Bragg, Fort Knox, and Fort Lee. His discharge papers came in 1967. Fogerty recalls in Bad Moon Rising: The Unofficial History of Creedence Clearwater Revival by Hank Bordowitz:
"The Army and Creedence overlapped, so I was 'that hippie with a record on the radio.' I'd been trying to get out of the Army, and on the steps of my apartment house sat a diploma-sized letter from the government. It sat there for a couple of days, right next to my door. One day, I saw the envelope and bent down to look at it, noticing it said 'John Fogerty.' I went into the house, opened the thing up, and saw that it was my honorable discharge from the Army. I was finally out! This was 1968 and people were still dying. I was so happy, I ran out into my little patch of lawn and turned cartwheels. Then I went into my house, picked up my guitar and started strumming. 'Left a good job in the city' and then several good lines came out of me immediately. I had the chord changes, the minor chord where it says, 'Big wheel keep on turnin'/Proud Mary keep on burnin'' (or 'boinin',' using my funky pronunciation I got from Howling' Wolf). By the time I hit 'Rolling, rolling, rolling on the river,' I knew I had written my best song. It vibrated inside me. When we rehearsed it, I felt like Cole Porter."