I recently read a book on ancient Indian history, but I can't remember the author so I'm not going to say too much about it. But it did stress how a great amount of knowledge of the period comes from Megasthenes, Greek ambassador of Seleucid I to a great Indian emperor, Sandrokottos (a name which does not appear in Indian sources, but is speculated to be Chandragupta Maurya). He wrote the famous Indika, a treatise on Indian culture, history, geography, flora, fauna. So the practice of embassies and ambassador-driven diplomacy goes back at least to the time of Alexander's successors (late 4th century BC).

Sources: McCrindle, J.W. (1877). Ancient India As Described By Megasthenes and Arrian.. Trubner & Co., London. http://www.archive.org/stream/ancientindiaasd02mccrgoog#page/n6/mode/2up