Graydon was born in 1832 Lisnakea a poor, isolated Irish village. He emigrated to the United States to escape the Potato Famine when he was 21 years old. Like many poor immigrants of the time, Graydon joined the army soon after arriving, and was posted to the southwest with the elite 1st Dragoons. They took the Santa Fe, and arrived in New Mexico in August of 1853. Graydon was posted to Los Lunas, a village south of Albuquerque along the Camino Real.
In 1861, when Confederate General Henry H. Sibley threatened to bring the Civil War into New Mexico, Graydon abandoned Casa Blanca and rode to Santa Fe to offer his services to the Union. Territorial Governor Henry Connelly awarded him with a commission to recruit a company of spies that would operate virtually independently of the Army. Graydon rounded up 100 of the “hardest cases” he could find, then reported to Colonel E.R.S Canby, the Commander of the Army in the territory, at Fort Craig. Many of the men Graydon recruited were former patrons of his saloon. They were an undisciplined lot, mean and nasty, but very good at collecting information and doing the kind of sabotage work that regular Army soldiers could not. Canby gave Grayson the mission of infiltrating the Confederate lines and sending back news about troop movements and numbers.