They are considered to have played a prominent role in the political history of medieval Bihar with many of their strongholds being established in the erstwhile Shahabad district of West Bihar, the most notable of which are Dumraon Raj and Jagdispur. Their oral tradition is contained within a 19th century book called the Tawarikh-i-Ujjaniya. According to this, they trace their ancestry to Ujjain where the Parmar Rajput kings ruled until their lands were occupied by tribal people. After settling in Bihar, the locals started to refer to them as Ujjainiya. They call themselves Ujjainiya Parmars.
Certainly by the 17th century, as documented in a text that they consider to record their history, and perhaps as early as the 14th century, the Ujjainiya Parmar Rajputs believed themselves to be related to the royal family of Ujjain in Malwa.They are descendants of Raja BHOJRAJ, Raja of Shahbad 1320/1333, younger brother of Mahalakadeva, last Parmar ruler of Dhar, migrated to Shahabad around 1320. He died 1333. . The oral tradition of the Ujjaniya, as written in the 19th century in a book called Tawarikh-i-Ujjaniya, makes a similar claim of a royal relationship. This document contains a family tree which claims to directly link the Paramara King, Bhoja to certain Ujjainiya chieftains in Bihar.
Arrival in Bihar and war with the Cheros
During the 14th century, the Ujjainiyas who were under the leadership of Hunkar Sahi, came into conflict with the Chero dynasty who were the traditional rulers of much of Bihar and Jharkhand. In the ensuing battles, both sides suffered many casualties with the Cheros losing more than 10,000 men however eventually the Chero rulers were expelled from Western Bihar and retreated to Palamau in modern-day Jharkhand. The conflict between the Ujjainiyas ans the Cheros lasted for centuries as many Cheros who remained resented the Ujjainiyas and continued to rebel against them by undertaking a protracted guerilla campaign against them.
Conflict with the Jaunpur Sultanate
Once the Ujjainiyas established sway over Western Bihar, they came into conflict with the Jaunpur Sultanate which lasted for more than 100 years. The Ujjainiyas responded to the Jaunpur Sultan, Malik Sarwar disturbing Brahmins in their prayers. The Ujjainiya chieftain, Raja Harraj was initially successful in protecting these Brahmins and defeating the forces of Malik Sarwar however the Ujjainiyas were defeated in subsequent battles and forced to hide in the forests and resort to guerrilla warfare.Later,Raja Omkar Dev effectively thwarted the onslaught of the Nawabs of Jaunpur. 
Battle of Surajgarha
The Ujjainiyas under the leadership of Raja Gajpati assisted Sher Shah Suri in the battle of Surajgarha against the Muslim rulers of Bengal who at the time were a major regional power. Raja Gajpati handpicked 2000 of his best men and was able to help Sher Shah Suri in achieving victory.General Ibrahim Khan was killed by Raja Gajpati and all the camp equipments,elephants and artillery pieces of the Bengal army fell into the hands of Ujjainiyas and Afgans.In return for their help the Ujjainiyas were entitled to any spoils of war they have found.Shershah Suri was so highly pleased with Gajpati's valvour that as a reward the region of Buxar was also assigned to him.Sher Khan also give his sword to Bairi Sal,the brother of Gajpati.
Role in military labour
The Ujjainiyas played a prominent role in the recruitment of Purbiya mercenary soldiers from Bhojpur for Muslim rulers, the Marathas and the British. For a period, their name was synonymous with the military labour market of Northern India.
- Ahmad, Imtiaz (2008). "State Formation and Consolidation under the Ujjainiya Rajputs in Medieval Bihar: Testimony of Oral Traditions as Recorded in the Tawarikh-i-Ujjainiya". In Singh, Surinder; Gaur, I. D. (eds.). Popular Literature And Pre-Modern Societies In South Asia. Pearson Education India. pp. 76–77. ISBN 978-81-317-1358-7. Retrieved 2 January 2012.
- Rajiva Nain Prasad (1968). "The Role of Ujjainiya Rajputs in the Political History of Bihar". Proceedings of the Indian History Congress. 30: 167–177. JSTOR 44141471.
- Bose, Saikat K. (2015). Boot, Hooves and Wheels: And the Social Dynamics behind South Asian Warfare. Vij Books India Pvt Ltd. pp. Formation_of_Rajput_identity. ISBN 978-9-38446-454-7.
- Kolff, Dirk H. A. (2002). Naukar, Rajput, and Sepoy: The Ethnohistory of the Military Labour Market of Hindustan, 1450-1850. Cambridge University Press. pp. 59–60. ISBN 978-0-52152-305-9.
- Brahmadeva Prasad Ambashthya (1961). "Tradition and Genealogy of the Ujjainiyas in Bihar". Proceedings of the Indian History Congress. 24: 351–352. JSTOR 44140725.
- Surendra Gopal (22 December 2017). Mapping Bihar: From Medieval to Modern Times. Taylor & Francis. pp. 289–295. ISBN 978-1-351-03416-6.
- Surinder Singh; I. D. Gaur (2008). Popular Literature and Pre-modern Societies in South Asia. Pearson Education India. pp. 77–. ISBN 978-81-317-1358-7.
- Md. Iftekhar Alam (1983). "The Relation of Bhojpur and Jaunpur (From 1389 A.D. to 1519 A.D". Proceedings of the Indian History Congress. 44: 213. JSTOR 44139839.
- Muhammad Iftekhar Alam (1991). "THE ROLE OF UJJAINIA CHIEFS OF BHOJPUR IN THE BATTLE OF SURAJGARHA (1530 A.D.): SUMMARY". Proceedings of the Indian History Congress. 52: 122–127. JSTOR 44142625.
- Dirk H.A. Kolff (2013). "Fighting for a Living: A Comparative Study of Military Labour 1500-2000". Fighting for a Living. Amsterdam University Press: 257. JSTOR j.ctt6wp6pg.11.