The pair initially made contact via message boards on Okayplayer.com and soon began recording and exchanging music. Soon after, they formed The Foreign Exchange without having ever met each other in person, hence the name. Their 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.
Foreign Exchange Music (often abbreviated as +FE Music) is a record label founded by The Foreign Exchange members Phonte and Nicolay. The label was first started for the release of their second album Leave It All Behind. Originally created for the release of their own music, the label has since issued albums for other acts.