You sort of ask two different questions. You ask which country had the first "intelligence agency" and then ask how intelligence services "became formalized."

You can reasonably say that "intelligence agencies" arose out of much earlier military intelligence. Military intelligence itself has existed in some form since time immemorial. Sun Tzu said in the Art of War "“If you know the enemy and know yourself, you need not fear the result of a hundred battles. If you know yourself but not the enemy, for every victory gained you will also suffer a defeat. If you know neither the enemy nor yourself, you will succumb in every battle.”

Formal military intelligence agencies, however, are a creature of the industrial age. John Keegan talks about this in Intelligence in War from Napoleon to Al Queda - (here's a seperate review )

However, an example of the way many leaders treated intelligence prior to the modern era is Admiral Nelson. Keegan notes Nelson, who largely eschewed any military intelligence, was hot on the heels of the french mediterranian fleet for weeks without knowing he was close. Napoleon himself was similiarly dismissive of military intelligence, one of his maxims was "All the information obtained from prisoners should be received with caution, and estimated at its real value. A soldier seldom see anything beyond his company; and an officer can afford intelligence of little more than the position and movements of the division to which his regiment belongs. On this account the general of an army should never depend upon the information derived from prisoners, unless it agrees with the reports received from the advanced guards, in reference to the position, etc., of the enemy."

Within the United States informal military intelligence existed as early as the revolutionary war, but a formal Bureau of Military information was established in 1863 by Major General JOeseph Hooker. The Bureau of military intelligence was run by Colonel George SHarp and John Babcock, a former pinkerton detective. It had 70 agents and set out to gather military information about confederate positions both through direct field work, agents, and interrogating enemy soldiers. Other states and army units also established their own intelligence units. You might look at THe secret war for the union, the untold story of military intelligence in the civil war

the bureau of military intelligence was disbanded in 1865, but some instituional memory remained. The office of naval intelligence was established in 1882 and tasked with learning about the navies of other countries. The Military intelligence division was founded in in 1885. THese however, never grew very large and were focused primarily on direct military intelligence.

British spy agencies typically trace their lineage to the Secret Intelligence Service which was established in 1909. It was a joint initiative of the admiralty and the war office, and was created specifically to spy on Imperial Germany. Its first commander was Captain Sir George Mansfield Smith-Cumming, who signed all his correspondence "C." Future leaders continued to sign correspondence as "C." This was, in part, the inspiration for "M" in Ian Fleming's James Bond stories.

The SIS was never terribly effective during WWI and never managed to establish an intelligence network within germany itself. But it developed during the interwar years becuase it had been tasked with investigating communist agencies and became probably the worlds most experienced intelligence service by 1939. At the outbreak of WWII at churchill's direction, the SIS, along with the foreign office and the war department, were directed to establish the Special Operations Executive a covert organization tasked with human intelligence and covert action.

When Roosevelt established the American Office of STrategic Services in 1942, its first leader, Bill Donovan explicitly looked at the british Special Intelligence Service as a model, and the first OSS officers were trained by SIS agents under British Security Coordination in Canada.

It is notable at the time that the SIS did not do any work in signals intelligence. That was handled under a seperate organization, the British Code and Cypher SChool. The Royal Air Force also had its own intelligence unit which did aerial reconissance.

However, within the US military it was in part the Office of Naval Intelligence along with Naval Communications units which provided cryptoanalysis for the US navy in the Pacific theater and broke Japanese codes.

Subsequent to WWII, the OSS formed the genesis of the CIA, and military code breaking units formed the genesis of the NSA. The military also retains its own internal intelligence units. The SIS remains the primary British Foreign intelligence agency.

In Russia as /u/SteveJEO notes, the CHeka, the committee for state security was established in 1917. Although not truly an intelligence organization, it became the origin of most of the soviet intelligence agencies including the KGB and GRU.

Peter the great established a secret police force in early 18th century Russia. It was an internal "intelligence" agency, not international like we're referring to here, but it served functions similar to their counterparts in modern bureaucracies like repressing and ferreting out political and religious dissidents, carrying out state sanctioned torture, and generally terrifying citizens into submission. Though I guess in that respect it was more of a precursor to the SS than it was to WWII era British intelligence agencies.

Source: Hughes,Lindsey

Peter the Great: A Biography

Yale UP

edit: source and spelling

I have by no means studied the question in depth but maybe the Cheka in 1917-18 as at least 'one' of the first major organisational attempts.

It should be noted though that the Cheka and following NKVD were internally orientated organisations concentrating on their own populace. A large amount of the development of the KGB was in response to a misplaced perception of British intelligence capability when in fact Britain had no such organisation.

(British intelligence instead was basically an old boys club of drunk diplomats throwing parties and talking to each other)