The archaeological findings and historical records from this period are scarce, and the exact location of kingdom's capital is unknown. It is thought to be somewhere between present-day Pekalongan or Jepara. A place named Keling subdistrict is found in northern coast of Jepara Regency, however some archaeological findings near Pekalongan and Batang regency shows that Pekalongan was an ancient port, suggests that Pekalongan might be an altered name of Pe-Kaling-an. Kalingga existed between the 6th and 7th centuries, and it was one of the earliest Hindu-Buddhist kingdoms established in Java. The historical record of this kingdom is scarce and vague, and comes mostly from Chinese sources and local traditions.^{[citation needed]}

Kalingga appeared in the 6th century which is thought to be located in the north of Central Java. Information about the Kalingga Kingdom is obtained from inscriptions and records from China. In 752, the Kalingga Kingdom became Sriwijaya's conquered territory because this kingdom was part of a trading network, along with the Dharmasraya and Tarumanagara Kingdoms which Srivijaya had previously conquered. The three kingdoms became strong competitors of the Srivijaya-Buddhist trading network.^[2]

The theory regarding contact between caliph Mu'awiyah with queen Shima of Kalingga has become a basis for further analysis about history of Islam in Minangkabau conference in 2011 and earlier conference about History of Islam in Indonesia in 1963, which researches suggested that the earliest contact of Nusantara civilizations with Islam were occurred in 7th AD century between Arabian peoples with southeast Asia, contrary to most popular belief that Islam were brought to Nusantara, particularly Java island, by Indian merchants and preachers.^[3] Azyumardi Azra, an Indonesian culture expert, accepted this Arab theory regarding the earliest contact of Islam in Java, although he also noted that the spread of Islam during queen Shima and Mu'awiyah era were not as vigorous as the later era in 15th AD century.^[4] The denomination of Arab theory which introduced by Hamka were supported by researcher who linked the founding of Islamic tomb in Barus, Sumatra island which traced in 7th AD century, thus establishing the theory regarding the existence of trade route between Kalingga kingdom, Srivijaya empire, and Umayyad caliphate.^[5]

The Chinese sources come from China and date back to the Tang Dynasty. In book 222 of the New history of the T’ang dynasty, it is stated that:

Ka-ling is also called Djava, it is situated in the southern ocean, at the east of Sumatra and at the west of Bali. At its south it has the sea and towards the north lies Cambodia.

The people make fortifications of wood and even the largest houses are covered with palm leaves. They have couches of ivory and mats of the outer skin of bamboo.^{[citation needed]}

The land produces tortoise-shell, gold and silver, rhinoceros-horns and ivory. The country is very rich; there is a cavern from which salt water bubbles up spontaneously. They make wine of the hanging flowers of the coco palm, when they drink of it, they become rapidly drunk. They have letters and are acquainted with astronomy. In eating they do not use spoons or chopsticks.^{[6]: 13 [7]}

It is stated that the king lives in a town called Djava, Djapa, or Djapo (闍婆). There is also a district called Lang-pi-ya on the mountains, identified by Groeneveldt as Dieng. Groeneveldt argues that Djapa may be referring to Japara, but he does not hold a firm belief in that.^{[6]: 13–15}

According to the Chinese Buddhist monk Yijing, in 664 a Chinese Buddhist monk named Huining (會寧 Huìníng) had arrived in Heling and stayed there for about three years. During his stay, and with the assistance of Jnanabhadra, a Heling monk, he translated numerous Buddhist Hinayana scriptures.^[8][9]: 79

In 674, the kingdom was ruled by Queen Shima, notorious for her fierce laws against thievery, which encouraged her people to be honest and uphold absolute truth. According to tradition, one day a foreign king placed a bag filled with gold at the intersection in Kalingga to test the famed truthfulness and honesty of the Kalingga people. Nobody dared to touch the bag that did not belong to them until three years later when Shima's son, the crown prince, accidentally touched the bag with his foot. The queen issued a death sentence to her own son but was overruled by a minister who appealed to the queen to spare the prince's life. Since it was the prince's foot that touched the bag of gold, it was decided that the foot must be punished through mutilation.^[8]

According to Indonesian historians seminar which organized by Aceh provincial government,^[10] and Hamka, queen Shima has managed to establish contact with Mu'awiya I ibn Abi Sufyan the first Umayyad caliph and fifth Qurayshite caliph.^[11][12][13] According to Reuben Levy, queen Shima regards Mu'awiyah as king of Ta-cheh in regards of Arab caliphate.^[14] Both Hamka,^[15] and Levy though that the envoys of Umayyad managed to reach Kalingga kingdom due to the improvements of caliphate maritime navigation, as Mu'awiyah were focusing the Early Caliphate navy at that time.^[14] Levy also gave figure that Mu'awiyah has possessed fleets as many as 5,000 ships in 655, which Levy predicted were the reason why the caliphate envoys manage to safely reach Kalingga during queen Shima reign, despite the length of distance between two nations.^[16]

According to Carita Parahyangan, a book composed in later period, Shima's great-grandson is Sanjaya, who is the king of Sunda Kingdom and Galuh Kingdom, and also the founder of Mataram Kingdom.^{[citation needed]}

Between 742 and 755, the kingdom had moved further east from the Dieng Plateau, presumably in response to the expansion of the Buddhist Sailendra dynasty.^[9]: 90

The Tukmas inscription was estimated to be originated from Kalingga period. It was discovered on the western slope of Mount Merapi, at Dusun Dakawu, Lebak village, Kecamatan Grabag, Magelang Regency, Central Java, and is written in Pallava script in Sanskrit tells about a clear spring water that is so sacred that adored as the analogue of holy Ganges's source in India. The inscription also bears Hindu signs and imageries, such as trisula, kamandalu (water jar), parashu (axe), kalacengkha (shell), chakra and padma (red lotus), those are symbols of Hindu gods.^{[citation needed]}

Another inscription dated from around the same period is the Sojomerto inscription, discovered in Sojomerto village, Kecamatan Reban, Batang Regency, Central Java. It is written in the Kavi script in Old Malay language and is estimated to be from the 7th century. The inscription tells about a ruler named Dapunta Selendra, the son of Santanu and Bhadrawati, and the husband of Sampula. Indonesian historian Prof. Drs. Boechari suggested that Dapunta Selendra was the ancestor of the Sailendras who later ruled in the Mataram Kingdom.

Both inscriptions suggest that in the 7th century, a Hindu Shivaist kingdom flourished on the northern coast of Central Java, now identified as the Kalingga Kingdom. Some of the oldest Javanese candis can also be found in the mountainous surrounding areas of northern Central Java, such as the Hindu temples of Dieng Plateau and the Gedong Songo temples, but they were probably built in a later period, during the early Mataram Kingdom. Historians suggest that there was a link between this old kingdom and the later kingdom that flourished in the southern part of Central Java, specifically the Kedu Plain, known as the Sailendra of the Mataram Kingdom.