Before the rise of the European colonial powers, the Malay peninsula and the Malay archipelago were home to empires such as the Srivijaya, the Majapahit (both ruled from Indonesia) and the Melaka Sultanate. The Srivijaya and Majapahit empires saw the spread of Hinduism to the region, and to this day, despite being nominally Muslim, many Hindu legends and traditions survive in tradtional Malay culture. Mass conversion to Islam only occured after the arrival of Arab traders during the Melaka Sultanate.
This was to change in the 16th century when the Portuguese established the first European colony in Southeast Asia by defeating the Melaka Sultanate. The Portuguese subsequently then lost Malacca to the Dutch. The British also establised their first colony on the Malay peninsula in Penang in 1786, when it was ceded by the Sultan of Kedah. Finally, the area was divided into Dutch and British spheres of influence with the signing of the Anglo-Dutch Treaty in 1824. With this treaty, the Dutch agreed to cede Malacca to the British and in return, the British ceded all their colonies on Sumatra to the Dutch. The line which divided the Malay world into Dutch and British areas roughly corresponds to what is now the border between Malaysia and Indonesia.
Before World War II, the Malay Peninsula was governed by the British as the Federated Malay States (Selangor, Perak, Negeri Sembilan and Pahang), which were governed as a single entity, the Unfederated Malay States (Johor, Kedah, Perlis, Terengganu and Kelantan), which were each governed as separate protectorates, and the Straits Settlements (including Malacca, Penang and Singapore), which were crown colonies. Northern Borneo consisted of the British colony of North Borneo, the Kingdom of Sarawak, which was ruled by a British family known as the "White Rajas", and the British protectorate of Brunei.
World War II was disastrous for the British Malayan Command. The Japanese swept down both coasts of the Malay Peninsula and despite fierce fighting, much of the British military was tied down fighting the Germans in Europe and those that remained in Malaya simply couldn't cope with the Japanese onslaught. The British military equipment left to defend Malaya were outdated and no match for the modern ones used by the Japanese, while the only two battleships based in the region, the HMS Prince of Wales and HMS Repulse, were sank by Japanese bombers off the East Coast of Malaya. By 31 January 1942, the British had been pushed all the way back to Singapore, which also fell to the Japanese on 15 February 1942. The situation was no different on Borneo, which fell to the Japanese on 1 April 1942 after months of fierce fighting.
After World War II, the Federated Malay States, Unfederated Malay States and the Straits Settlements of Malacca and Penang were federated to form a single British colony known as the Malayan Union, with Singapore splitting off to form a separate colony. In the Malayan Union, the sultans of the various states ceded all their powers except those in religious affairs to the British crown. However, widespread opposition to the Malayan Union led the British to reconsider their position, and in 1948, the Malayan Union was replaced by the Federation of Malaya, in which the executive positions of the sultans were restored. In Borneo, the White Rajas ceded Sarawak to the British crown in 1946, making it a crown colony of the United Kingdom.
Malaya gained independence from the British in 1957. The Union Jack was lowered and the first Malayan flag was raised in the Merdeka (independence) Square on midnight 31st August 1957.
Six years later, Malaysia was formed on 16th September 1963 through a merging of Malaya and Singapore, as well as the East Malaysian states of Sabah (known then as North Borneo) and Sarawak on the northern coast of Borneo, with Brunei deciding not to join. The first several years of the country's history were marred by the Indonesian confrontation (konfrontasi) as well as the Philippines' claims to Sabah. Singapore was expelled from the federation on 9th August 1965 after several bloody racial riots, as its majority Chinese population and the influence of the People's Action Party led by Lee Kuan Yew (later the long-ruling Prime Minister of Singapore) were seen as a threat to Malay dominance, and it became a separate country.
Malaysia is a constitutional monarchy, nominally headed by the Paramount Ruler (Yang di-Pertuan Agong), who is "elected" by the sultans for a five-year term from among the nine sultans of the Malay states, though in practice the election usually follows a prescribed order based on the seniority of the sultans at the time of independence. This gives Malaysia a unique political system of rotational monarchy, in which each of the sultans would take turns to be the king of Malaysia. The current king, from Terengganu, was sworn in on 13 Dec 2006.
Malaysia's government is largely based on the British Westminster system, consisting of a bicameral national parliament, with each of the states also having their own unicameral Dewan Undangan Negeri (State Legislative Assembly). The lower house, known as the Dewan Rakyat (Hall of the People) is elected directly by the people. The upper house, known as the Dewan Negara (National Hall), consists of 26 members elected by the state governments, with each state having 2 representative, while the remaining members are appointed by the king. The head of government is the Prime Minister, who is the party leader of the winning party in the lower house. The United Malays National Organisation (UMNO) party and its National Front (Barisan Nasional) coalition have ruled Malaysia uninterrupted since its independence, and while periodic elections are contested by feisty opposition parties, the balance has so far always been shifted in the government's favor, partly due to press control and use of restrictive security legislation dating from the colonial era.
In practice, the king is only the nominal Head of State, while the Prime Minister is the one who wields the most authority in government.