The pair first made contact over message boards on Okayplayer.com and began recording and sending music back and forth. Soon after, they formed The Foreign Exchange without having ever met each other in person, hence the name. The album, Connected, was released in 2004 and was a showcase for Nicolay's musical talents as well as an introduction to like-minded Little Brother affiliates who contributed to the album. The album received strong reviews and the single, "Sincere", featuring YahZarah, was released with a promotional video.
In June 2009, the group announced that Zo! is now an official artist on The Foreign Exchange Music imprint and, in November 2009, YahZarah also joined the imprint. Median and Darien Brockington later joined.
In December 2009, the group were nominated for a Grammy Award, for Best Urban/Alternative Performance for the track "Daykeeper" (feat. Muhsinah) from their Leave It All Behind album.