According to the Nagarakertagama, and supported by inscriptions dating from the late 13th and early 14th centuries, Raden Wijaya Sri Kertarajasa Jayawardhana married the four daughters of Kertanagara. From his eldest and principal queen, Dyah Dewi Tribhuwaneshwari, was born a son, Jayanagara, who succeeded to the throne on his father's death in 1309.

During the reigns of both Kertarajasa and Jayanagara the focus was on the establishment of stability within the new state. Numerous uprisings occurred, all of which were put down successfully, though not without cost of lives. Then, in 1328, Jayanagara was assassinated. It is said that he was overprotective towards his two half sisters, born from Kertarajasa's youngest queen, Dyah Dewi Gayatri. Complaints lodged by the two young princesses led to the intervention of Gajah Mada, the talented minister who was later to take Majapahit to the height of its glory. He arranged for a surgeon to murder the king while pretending to perform an operation.
With the death of Jayanagara the throne of Majapahit was without a direct male heir. The position was occupied instead by the eldest of the deceased king's two sisters, Tribhuwana Wijayatungga Dewi, who ruled until 1350. By that time her son, Hayam Wuruk, who had been born in 1334, became old enough to take over. During his reign, as well as that of his mother, effective power was in the hands of Gajah Mada, who had been appointed prime minister and commander-in chief.
Gajah Mada stands among the greatest of Indonesia's heroes. From the time when he swore his famous oath of allegiance, the Sumpah Palapa, until his death in 1364, a period of just 28 years, he succeeded in spreading the power and influence of Majapahit throughout the archipelago, and even beyond the boundaries of the present day Republic of Indonesia.