I take it you specifically mean resident ambassadors rather than simply representative embassies in general -- forms of diplomacy are, from what we know of anthropology, as old as human politics itself. The modern system of permanent embassies is very much a Renaissance-era innovation. Garrett Mattingly's Renaissance Diplomacy (1955) is still the definitive work on this development, though it's been expanded more recently by e.g. M. S. Anderson, The Rise of Modern Diplomacy (1993) and Daniela Frigo, Politics and Diplomacy in Early Modern Italy (2000).

To the extent that something similar to a resident system may have existed in ancient history -- for example the papal representatives in Constantinople in late antiquity -- it wasn't ultimately influential to the development of the modern system, which happened far removed in time and without much knowledge of any earlier precedents. Bear in mind that the modern state system is quite distinctive and in some respects the role of the ambassador only makes sense on its terms (the history of international political thought is an important emerging field at the moment and focuses on this question more broadly).

The first actual resident diplomats emerge around the 14th century in the Italian city states, though there are medieval roots in the system of heralds. The first resident agent we know of, according to Mattingly, is a Mantuan representative at the court of Emperor Louis the Bavarian around the 1340s, and there was probably also another Mantuan at Ferrara. (Mantua and Ferrara were Italian city-states.)

Over the course of the fifteenth century, more of these began to appear in Italy, and the role of the permanent ambassador became more defined in political thinking. De officio legati (c. 1490), by Ermolao Barbaro, a Venetian resident agent at Rome, is among the first essays specifically about the role of an ambassador, and this quickly became an expansive Italian literature about the ideal figure of the diplomat.

From the early 16th century on, the system of new diplomacy developed in Italy spread across Europe. Spain, France, the Empire (in union with Spain), and England all appointed residents -- in England a sort of foreign service developed under the supervision of Thomas Wolsey. By the time of the advent of the Thirty Years' War in 1618, the new system was entrenched in Europe, and the idea of diplomatic immunity had emerged (see Linda and Marsha Frey, The History of Diplomatic Immunity, pp. 116ff.). So by that time the practice of ambassadorial residency was well-established.

This is admittedly a Western-centric analysis, but of course the modern ambassadorial system is fundamentally one that developed in Europe. From my knowledge of the East Asian state system, for example, there were not, traditionally, equivalents to the accredited resident agents or ambassadors of Europe.