Alegria was created by Republic Act No. 5239. It was originally the sitio of Anahaw founded by immigrants from the municipality of Bacuag. Sitio Anahaw was situated near Lake Mainit, and would often be flooded due to heavy rains. During rainy seasons, the local families transferred to a place now called Alegria.
The name Alegria was derived from the Spanish word which means "lively". Its name was given by Judge Sixto Olga who happened to spend a night in the place. The people offered him a party dance. Because their affair was lively he told the people to change the name Anahaw to Alegria. 
Alegria became a barrio in 1927. It was formerly one of the biggest barrios in the municipality of Mainit. The municipality extends from the boundary of Kitcharao, Agusan del Norte, to Pungtod and Dayano that is the boundary of the mother municipality of Mainit.