Harmony was released in May 2004 by Linus Entertainment (Linus/Warner in Canada and SpinART/Ryko in the U.S.). It was an album that almost never happened. Lightfoot had laid down demo tracks for the record not long before he suffered a near-fatal ruptured artery in September 2002. During his recovery, in whose course he lost enough weight for his appearance to become shockingly gaunt, he directed the recording of backing tracks and was well enough by the time it was released to begin touring again. He says in the liner notes: "In the final analysis, the job was what mattered. It was good being preoccupied in a very constructive way with a project in the works; one which would carry itself forward, right up through the artwork and editorial, until its ultimate completion." The album was generally well received.
In his Allmusic review, critic James Christopher Monger praised the album but also wrote "By no means as inspired as the classics Summertime Dream and If You Could Read My Mind, Harmony listens like a good book, and fits snugly into the impressive Lightfoot canon."