Sutoyo was born in Karanganyar, Kebumen, Central Java. He finished school before the Japanese invasion in 1942, and during the Japanese Occupation, he studied governmental administration in Jakarta. He then worked as a government employee in Purworejo, but resigned in 1944.
After the Indonesian Declaration of Independence in 1945, Sutoyo joined the Police section of the People's Security Army (TKR), the forerunner of the Indonesian Army. This then became the Indonesian Military Police. In June 1946, he was appointed adjutant to Colonel Gatot Soebroto, commander of the Army Police. He rose steadily through the ranks within the Military Police, and in 1954 became chief of staff at Military Police Headquarters. He held this position for two years before being posted to London to serve as the assistant military attaché at the Indonesian embassy. After training at the Army Staff College in Bandung from 1959-1960, he was appointed acting Army judicial inspector, then because of his legal experience, in 1961 he was appointed to the post of judge advocate general of the Army.
According to the official account by the Government of Indonesia, he was kidnapped in the early hours of 1 October 1965. Members of the 30 September Movement led by Sergeant Major Surono entered Sutoyo's house on Jalan Sumenep, Menteng, Central Jakarta. They gained entry through a garage at the side of the house. They forced his maid to hand over the key, entered the house and told Sutoyo he had been summoned by President Sukarno. They then took him to their base at Lubang Buaya. There, he was killed and his body thrown into a disused well. Like those of his other murdered colleagues, his body was recovered on 4 October and he was given a state funeral the next day. He was posthumously promoted to Major General and made a Hero of the Revolution.