Who started the first official spy agency in the world? By spy agency, I mean a dedicated team under the control of a ruler, who specialize in intelligence gathering and counter espionage. Something similar to the French Secret or the Shinobi or MI6.
An early military writer to discuss the use of spies for military purposes was Sun Tzu in the "Art of War." So it's fair to say that Chinese governments were using spies on an organized basis as early as the 5th to 6th century B.C.
Pre-dating the usage of spies by the Persians is (perhaps unsurprisingly) the Ancient Egyptian use of spies and military intelligence, from at least the New Kingdom period (late 2nd milleniunm B.C.) onwards, but quite possibly even from the Old Kingdom. period (early 3rd millenium B.C.), as suggested by the reference to "early Pharaohs" in the following source.
This source describes the ancient usage of spies by the Egyptians, and lists evidence as hieroglyphs discovered in Egypt.
Historical and literary accounts of spies and acts of espionage appear in some of world's earliest recorded histories. Egyptian hieroglyphs reveal the presence of court spies, as do papyri describing ancient Egypt's extensive military and slave trade operations. Early Egyptian pharos employed agents of espionage to ferret-out disloyal subject and to locate tribes that could be conquered and enslaved. From 1,000 B.C. onwards, Egyptian espionage operations focused on foreign intelligence about the political and military strength of rivals Greece and Rome.
The same article also mentions employment of spies by in ~500 B.C. by the Ancient Chinese, and by Greek and Roman leaders, all of which post-date the Egyptian use by many centuries. The first paragraph of the article does in fact allude to even earlier spies in written history: "Espionage is one of the oldest, and most well documented, political and military arts. The rise of the great ancient civilizations, beginning 6,000 years ago in Mesopotamia, begat institutions and persons devoted to the security and preservation of their ruling regimes.", though it does not provide any direct evidence.
Darius I "the Great" (549-486 BC), one of the early kings of the ancient Achaemenid (Persian) Empire was well-known for employing many spies (known as the "king's ears") in his service.
This well-documented usage of spies by the early Persian king is at least as early, if not earlier than Sun Tzu's mention of spies in the Chinese histories. I would also consider it quite likely that Darius I inherited this practice from even earlier Persian kings, and perhaps even other cultures he conquered.
From this source on the Acaemenid Empire
Darius realized that if the Empire were to work it needed efficient organization. He divided it into 20 satrapies, or provinces, each paying a fixed rate of tribute to Persia. Each satrapy was run by a centrally appointed satrap, or governor, often related to Darius. To prevent the satrap building a power base, Darius appointed a separate military commander answerable only to him. Imperial spies known as the ‘king’s ears’ kept tabs on both and reported back to Darius through the postal service – the Empire was connected by a network of roads along which couriers could change horses at stations spaced a day’s travel apart.
I cannot recall the exact verse but in the Bible there are refrences to roman spies, if that helps.
Edit by somebody without a login: Joshua 2:1 explicitly refers to spies
And Joshua the son of Nun sent out of Shittim two men to spy secretly
(Source, quote is from King James version)
and Numbers 13 may refer to spies or to scouts:
Send thou men, that they may search the land of Canaan, which I give unto the children of Israel: of every tribe of their fathers shall ye send a man, every one a ruler among them.
(Source, quote is from King James version)
These would both be about 1100 BC.
Much later than the Egyptians, I know, but in the 4th century CE the Roman Empire had a well-established spy network known as the agentes in rebus (agents on matters). The historian Ammianus Marcellinus describes their activities e.g. a dinner party in Spain, where a guest comments that a purple tablecloth could be turned into an imperial robe (purple being the colour of imperial power) with the result that all the guests were tracked down and eliminated by the agentes in rebus. Apparently there were five grades of agents controlled by a director reporting to a senior official in the imperial bureaucracy. One director was called Paulus Catena - Paul the Chain - because of his ingenuity in piecing together the intricate links that made up a typical conspiracy.