"Within six hours, we must make a decision on a petition and there was not a strong enough suspicion, so he was released," Karin Rosander, communications director at the regional public prosecution office, told news agency TT.
Rosander had no information on what would happen to the 28-year-old man, a Canadian citizen of Pakistani origin.
"He is free to go where he wants," she said. "According to police, the man will receive help with accommodation for the night and then continue his trip tomorrow."
The was arrested earlier on Saturday for "planning to sabotage an airplane," police operations director Stefan Rådman told AFP.
However, police in Sweden said no explosives were found in the search.
The plane, a Boeing 777 operated by Pakistan International Airlines, was on its way from Toronto to Karachi, Pakistan when it was forced to make an emergency landing at Arlanda after 7:30 am.
The landing was prompted after Canadian police, through the country's air traffic authorities, contacted the pilot in the air and said that there may be a suspicious person on board.
Shortly before 7 am local time, the pilot contacted air traffic control at the airport and requested landing rights, saying there a person suspected of having explosives on board.
Passengers were evacuated from the plane and led inside the terminal two hours after landing, where they received food and assistance.
The airplane left for Manchester at 5 pm local time to continue its journey to Karachi because the crew was too tired to complete the flight to Pakistan, Arlanda airport spokesman Jan Lindqvist said.
Regular air traffic at Arlanda is unaffected by the threat. Terminals are open as usual and all remaining flights are leaving on schedule.
"We have so much capacity that we can put a plane to the side so that it doesn't affect other traffic," Anders Bredfell, press director at the airport, told TT earlier on Saturday.
A PIA spokesman told AFP some 243 passengers and 18 crew members were on board.
"PK782 was coming to Karachi form Toronto. As soon as the aircraft entered the European airspace, it was asked by the control tower to land in Stockholm as there was some threat," spokesman Syed Sultan Hassan told AFP. "The pilot informed our central control here that he was landing in Stockholm."
According to Janne Hedlund of the Stockholm county police, the mood on the plane was calm, which may be because passengers were not informed about the real reason why the plane landed at Arlanda until they were evacuated.
"No, they did not know exactly what had happened," said PIA's Hassan. "They learned that the staff in Stockholm had received information from Canadian police that they had to land."
Police officials said the man was not on any international no-fly lists and had cleared a security check in Canada. The accused man was arrested as the plane was evacuated.
"He's made it through all security checks and screenings and hasn't come up in any similar type of situation previously," said Hedlund.
The arrest proceeded smoothly and he did not resist when taken into custody.
"He was a littled irritated when he was arrested, but quiet," said Rådman.
Separately, Canadian police said Saturday they were looking into whether the bomb alert was a hoax. Under Canadian law, a "terrorist hoax" is a crime punishable with prison time, a spokesman with the Royal Mounted Police in Toronto, Marc Laporte, told AFP.
"It was a woman who contacted the Canadian police and said there was a man onboard who could have explosives with him. It remains unclear who the woman is," said Hedlund.