Mraz became a fan of Caillat after hearing her music on MySpace. He then called her to see if she'd want to write and sing together. In an interview with VH1, Mraz stated that he "played a songwriting game" with friends to see how the lyrics would go. Mraz and Caillat performed the song on Saturday Night Live on January 31, 2009. They performed the song again on The Ellen DeGeneres Show in February.
"Lucky" debuted on the Billboard Hot 100 at number 96 for the issue dated January 31, 2009. On the same week it had a debut on the Pop 100 chart at 84 and moved to a peak of 48. The next week the song rose to number 84 on the Hot 100 and peaked at number 48. On the Hot Adult Top 40 Tracks, the song is already a Top 10 hit, reaching #9.
The song has also charted on the Dutch Top 40 at number 27 and moved to peak of 8.
On the Canadian Hot 100 charted on 70 and moved to 56. The song re-entry on the Canadian Charts on the issue of April 30, 2009 at #99.
The video was shot in Prague, Czech Republic and the island of Kauai in Hawaii and was released January 16, 2009. Mraz and Caillat's parts in the video were filmed separately. The video follows the context of the song, featuring Mraz and Caillat singing their verses.
The video starts with a shot of Old Town city square in Prague. Mraz is shown getting ready to meet somebody. Caillat is in a hilly seaside area in Hawaii and sits on the beach as the song starts. Mraz gets ready and goes out to the square. Caillat continues to sing the song walking beside the sea and playing with her scarf. Mraz and Caillat sing the song with both in separate places. Scenes are interspersed with the scene of a car zooming inside and Mraz ultimately reaches Old Town Square in Prague and stands in front of the Jan Hus Memorial Statue. Both Mraz and Caillat look back and the video ends with the implication that both of them see one another.