Malaita was, along with the other Solomon Islands, settled by Austronesian speakers between 5000 and 3500 years ago; the earlier Papuan speakers are thought to have only reached the western Solomon Islands. However, Malaita has not been archaeologically examined, and a chronology of its prehistory is difficult to establish. In the traditional account of the Kwara'ae, their founding ancestor arrived about twenty generations ago, landed first on Guadalcanal, but followed a magical staff which led him on to the middle of Malaita, where he established their cultural norms. His descendents then dispersed to the lowland areas on the edges of the island.
Malaita was first known to Europeans by the Spaniard Alvaro de Mendaña de Neira in 1568. An account by his chief pilot, Hernando Gallego, establishes that they called the island Malaita after its native name and explored much of the coast, though not the north side. The Maramasiki Passage was thought to be a river. At one point they were greeted with war canoes and fired at with arrows; they retaliated with shots and killed and wounded some. However, after this discovery, the entire Solomon Islands chain was not found, and even its existence doubted, for two hundred years. After it was re-discovered in the late 18th century, Malaitans were subjected harsh treatment from whaling boat crews and blackbirders. However, contact with outsiders also brought new opportunities for education. The first Malaitans to learn to read and write were Joseph Wate and Watehou, who accompanied Bishop John Coleridge Patteson to St John's College, Auckland. Later, many labourers learned to read and became Christian, and some were disappointed with the Australian decision to repatriate its workers as part of the White Australia Policy. The skills of literacy and protest letters was a precedent for the later Maasina Ruru movement.
Many of the earliest missionaries, both Catholic and Protestant, were killed, and this violent reputation survives in the geographic name of Cape Arsacides, the eastward bulge of the northern part of the island, meaning Cape of the Assassins. However, some of the earliest missionaries were Malaitans who had worked abroad, such as Peter Ambuofa, who was baptised at Bundaberg, Queensland in 1892, and gathered a Christian community around him when he returned in 1894. In response to his appeals, Florence Young led the first party of the Queensland Kanaka Mission (the ancestor of the SSEC) to the Solomons in 1904. Anglican and Catholic churches also missionized at this point. As the international labour trade slowed, an internal labour trade within the archipelago developed, and by the 1920's thousands of Malaitans worked on plantations on other islands.