In a somber televised address, Defense Minister Awad Ibnouf announced "the toppling of the regime" and said Bashir had been detained in "a secure place," bringing an end to his three-decade rule.
A transitional military council will replace the president for two years, he said, adding that the country's borders and airspace would be shut until further notice.
But in a warning to protestors, he also imposed a night-time curfew from 10:00pm (2000 GMT) to 4:00 am (0200 GMT).
Bashir, who swept to power in a 1989 coup, was one of Africa's longest-serving presidents. He is wanted by the International Criminal Court on charges of genocide and war crimes.
But organizers of the protests, which first erupted in December, rejected the army's move and vowed to keep up their campaign until the whole regime was swept aside.
"The people do not want a transitional military council," said Alaa Salah, who became an icon of the protest movement after a video of her leading demonstrators' chants outside army headquarters went viral.
"Change will not happen with Bashir's entire regime hoodwinking Sudanese civilians through a military coup," she tweeted.
"We want a civilian council to head the transition."
The protestors' Alliance for Freedom and Change said the regime had "conducted a military coup by bringing back the same faces and the same institutions which our people rose against."
It urged people "to continue their sit-in in front of army headquarters and across all regions and in the streets."
'We're not leaving'
Since early Thursday morning, huge crowds of jubilant Sudanese had filled squares across the center of Khartoum as the army promised an "important announcement."
Chanting "the regime has fallen," they poured into the open ground outside army headquarters, where defiant protesters had braved tear gas and gunfire to keep up an unprecedented sit-in, now in its sixth day.
But the festive mood later soured, as protestors chanted: "We don't want Ibnouf!"
"We are not leaving, we are not leaving. Just fall and that's all," they shouted.
The opposition Sudanese Congress Party called on the military council to dissolve itself and form "a joint military and civilian council to run the government for a four-year transition term."
It also urged the army to give executive powers to civilians.
Adel, a protestor outside army headquarters, said Thursday's announcement meant "we have not achieved anything."
"We will not stop our revolution. We are calling for the regime to step down, not only Bashir," he said.
Army vehicles carrying troops were seen deploying across the center of Khartoum from early Thursday.
Troops raided the offices of the Islamic Movement, the ideological wing of Bashir's ruling National Congress Party, witnesses told Agence France-Presse.
Martial music was played on state television as soldiers ordered the TV to halt its normal programming ahead of Ibnouf's announcement.
Outside army headquarters, dozens of joyful protesters early Thursday climbed on top of landcruisers and armored vehicles that had been posted to protect them from intervention by other branches of the security forces.
Braving the searing 42 degree Celsius (108 degree Fahrenheit) heat, they hugged and kissed soldiers in the crowd.
The military council said it was declaring a ceasefire across the country, including in war-torn Darfur.
Meanwhile, Sudan's feared intelligence service said it was freeing all the country's political prisoners, state media reported.
"The National Intelligence and Security Service has announced it is releasing all political detainees across the country," the official SUNA news agency said.
But in the eastern cities of Kasala and Port Sudan, the releases failed to materialize, prompting protesters to storm NISS buildings, witnesses said.
That came despite protest organizers urging demonstrators to refrain from attacking government figures or buildings.
Demonstrators have spent 5 nights defiantly camped outside the sprawling army headquarters complex in Khartoum, which also houses Bashir's official residence and the defense ministry.
"We had enough of this regime – 30 years of repression, corruption, rights abuses, it's enough," said one protester at the sit-in.
The demonstrators have braved repeated volleys of tear gas from NISS members since they began camping outside the complex on Saturday, April 6, protest organizers say.
Officials say 49 people have died in protest-related violence since the demonstrations first erupted in December.
Neighboring Egypt, where President Abdel Fattah al-Sisi came to power in similar circumstances, said Thursday it supported the Sudanese people and the army in their political transition. – Rappler.com