Woodlands Naval Base was a military base of the Royal Malaysian Navy in Woodlands, Singapore. It is on the opposite side of the Singapore Strait from Johor Bahru. This base served as the first headquarters of the Royal Navy Malay Section (then name of the Royal Malaysian Navy) from 1952 until 9 September 1984, when the headquarters relocated to Lumut, Perak.

This base was part of Singapore Naval Base and was called Singapore Naval Base - Woodlands Side. After the British Government transferred the Royal Malayan Navy (then name of the Royal Malaysian Navy) to the Federation of Malaya on 1 July 1958, almost a year after the Federation of Malaya gained independence from the British, the Singapore Naval Base was divided in half, with the Woodlands side being given to the Federation of Malaya and the Sembawang side remaining under the British and Commonwealth's military.

The Singapore Naval Base was constructed between 1928 and 1938. It is intended to be the regional headquarters for the Royal Navy. In 1934, the British Administration in Malaya began to establish the Straits Settlements Naval Volunteer Reserves (SSNVR) in Singapore, but at the time, only European descendants were permitted to enlist. The only non-European member of the volunteer navy force is Sergeant Major Adnan bin Raji from the Straits Settlements Volunteer Force. Sergeant Major Adnan was transferred to the naval force and given the rank of Chief Petty Officer in order to serve as a Drill instructor. The SSNVR was relocated to HMS Laburnum in Telok Ayer (now Outram, Singapore) in 1939. The year 1938 saw the formation of the first local naval volunteer force in Gelugor, Penang. Due to a positive response from the locals, the Royal Navy began recruiting local Malay individuals as full-time officers and sailors and establishing the Royal Navy Malay Section. This section is subsequently known as the Malay Navy and is stationed at the Singapore Naval Base.

HMS Pelandok was commissioned as the new designation for the Sembawang side of the Singapore Naval Base. Additionally, HMS Pelandok also functions as a training facility for the Royal Navy Malay Section. Following World War II, the British naval forces in Malaya could not be maintained economically. Since Japan's surrender in September 1945, even without full naval capability, the Royal Navy has begun repairing HMS Pelandok. By the end of 1951, the restoration would have been finished. On 21 January 1948, the Federation of Malaya and the Colony of Singapore reached an mutual agreement to re-establish a joint bi-national naval force, The Malayan Naval Forces (MNF), from the remnants of the Royal Navy Malay Section. The MNF became the Royal Malayan Navy on 23 May 1952, when Queen Elizabeth II granted the MNF Royal status for their service during the Malayan Emergency. This included the expansion of the navy's base. The land in Woodlands that was unused was explored and handed over to the Royal Malayan Navy. This new area, also known as Singapore Naval Base - Woodlands Side, later received the designation HMS Malaya in honour of the British battleship HMS Malaya from World War I.

On 31 August 1957, the Federation of Malaya gained independence from the British. As a young nation, the military was transferred in stages. The British government transferred the Royal Malayan Navy and the Singapore Naval Base - Woodlands Side to the Federation of Malaya on 1 July 1958, while the British and Commonwealth military still occupied Sembawang's side. Simultaneously, the HMS Malaya was renamed KD Malaya, and Singapore Naval Base - Woodlands Side, was renamed Woodlands Naval Base.

On 16 September 1963, Singapore obtained independence from the British by merging with the Federation of Malaya to form Malaysia. All of the military units, including the Naval forces, were merged. Due to a number of reasons, Singapore was expelled from Malaysia on 7 August 1965. The 1948 agreement between the Federation of Malaya and the Colony of Singapore grants Malaysia rights to the Woodlands Naval Base, which it continues to operate as the headquarters of the Royal Malaysian Navy.

Since the end of 1980, Malaysia has been relocating the Royal Malaysian Navy (RMN) headquarters to the Lumut Naval Base. The Royal Malaysian Navy Training Centre (designated KD Pelandok in honour of HMS Pelandok) and six navy ships are the first to be relocated from Woodlands Naval Base. The Malaysian government finished the relocation of the RMN Headquarters to Lumut, Perak, on 9 September 1984. The Woodlands Naval Base continues to operate under RMN, but it is now more of a specialised training centre for navy ratings. Since 1992, Singapore has tripled the rent for this naval base, but it is continuing to operate under RMN until 1997.

In 1997, the Malaysian government handed over the Woodlands Naval Base to Singapore. The Singaporean government then converts the naval base's buildings into Admiralty West Prison. The prison was operational until July 2018, when it was relocated to Tanah Merah. The naval jetty of Woodlands Naval Base was converted into Woodlands Waterfront Park in 2011 and opened to the public.

All buildings at Woodlands Naval Base were demolished in 2021, with the exception of the administration building, to make way for housing complexes. The administration building is left standing because of its historical significance to the Republic of Singapore Navy and the Royal Malaysian Navy. The Singapore Urban Redevelopment Authority stated on 14 February 2022, that the administration building must be included in any future development of the Woodlands Naval Base's area.