Kenneth Franklin Shinzato is a civilian who works on Kadena Air Base.
Police say information from the suspect led them to the body of Rina Shimabukuro, which was lying by the side of a road.
Police say the suspect confessed to attacking the woman and abandoning her body. Sources close to the investigation say police found the victim's bloodstains in his car.
Residents have long complained about crimes committed by base personnel. More than 70 percent of US military facilities in Japan are concentrated in the prefecture.
"This is unforgivable. I'm lost for words," says one local resident.
"Incidents like this will happen as long as we have the bases," says another.
Japan's Prime Minister Shinzo Abe voiced his anger.
"I demand that the US respond in a strict manner to absolutely make sure similar incidents do not happen again," Abe said.
Pentagon officials expressed shock and dismay about what they called a "tragic" incident.
"I want to assure you that the Secretary of the Department of Defense is determined to provide complete cooperation to the government of Japan and the local authorities in Okinawa regarding this investigation," said Pentagon Press Secretary Peter Cook.
Cook said Defense Secretary Ash Carter is also expressing condolences and sympathies to the victim's family and friends.
Impact of Okinawa Murder
Yoichiro Tateiwa
The incident could be a serious obstacle for the ongoing negotiation over where to relocate the Futenma air base.
It's also not the first time that an attack on a citizen of Okinawa has strained relations in the prefecture.
A change-of-command ceremony was held on Friday for US marines stationed in Okinawa.
"I know everybody here knows that Congress hold us accountable to be most ready when the nation is least ready. That's our chapter. That's in our DNA. It's what we do, to be most ready," said Marine Corps Lt. Gen. Lawrence D. Nicolson.
The murder of Rina Shimabukuro and the arrest of a base employee as the only suspect was not mentioned. But that shows how sensitive the case is to the US forces.
Governor Takeshi Onaga opposes relocating the US marine Futenma air base within the prefecture. When he heard about the murder, he did not hide his outrage.
"The fact that this happened because of the presence of US bases is extremely regrettable," Onaga said. "I'm of course angry, but also speechless as I look back at the developments to date."
The Japanese government was quick to take action. Foreign Minister Fumio Kishida summoned US Ambassador Caroline Kennedy.
"It is extremely regrettable that the brutal and heinous act took place. I am lodging a strong protest on behalf of the Japanese government," Kishida said.
The suspect worked at Kadena air base, the biggest US airfield in the region. A Japanese policeman is guarding the main gate of the faciilty, which is unusual. Not many US military personnel use it.
Local people say whenever an incident like this happens, US forces restrict US personnel from going off-base.
For past incidents, the US military has issued curfews and promised to tighten discipline. But many people in Okinawa question whether such measures actually work.
In 1995, 3 US servicemen gang raped a local Japanese schoolgirl. The attack sparked massive protests against US military bases in Okinawa.
It led to the agreement between Japan and the United States to relocate Futenma Air Station and return the land.
But more than 20 years on, controversy continues over where the US facility should be moved.
Meanwhile, crimes by US soldiers in Okinawa continue to happen. In March this year, a US Navy sailor was arrested for the alleged sexual assault of a Japanese woman.
The latest incident has citizens again taking to the streets in protest. Sources close to the Japanese government say it could fuel even more protests against US bases in Okinawa.
They say it could also lead to a shake-up of the Japanese security alliance.
US President Barack Obama will be in Japan next week for the Group of Seven summit in Ise-Shima. He is also scheduled to visit the atomic-bombed city of Hiroshima.
It is not clear whether the incident will have an effect on the visit. But many people in Okinawa say it's clear that it will have an effect on the relocation of Futenma air base.