The Federated Malay States Railways (FMSR) was a consolidated railway operator in British Malaya (present day Peninsular Malaysia and Singapore) during the first half of the 20th century. Named after the then recently formed Federated Malay States in 1896 and founded five years after the formation of the federation, the company acquired various railways that were developed separately in various parts of Malaya, and oversaw the largest expansion and integration of the colonial rail network encompassing the Federated Malay States, the Unfederated Malay States (except Trengganu) and the Straits Settlements, with lines spanning from Singapore in the south to Padang Besar (near the border with Siam) in the north.

Until the formation of the FMSR, Malaya's railway systems were fragmented and concentrated in the commercially active west coast of the peninsula; none of the systems were originally intended for interstate travel, and were founded to fulfill specific purposes. By the end of the 19th century, Malaya had at least six separate railway companies:

The formation of the Federated Malay States (FMS) in 1896 led to a centralisation of Residential power and improved co-ordination of development in the new founded federation. In the same year, the newly appointed residents-general of the FMS, Frank Swettenham, proposed a master plan to extend and connect railway networks within the FMS and Province Wellesley.

Swettenham's proposal encompassed three phases: The first was to be the construction of a "development" line towards the north that would connect Perak's railways with those of Selangor's and the Province Wellesley's, while running through valuable but underdeveloped land in between; the second phase consisted of an extension of the line to Kuala Lipis, Pahang's then administrative capital, to promote the development of the state's mineral industry; the third section was to be a southwards extension from the Selangor Railway's southern terminus in Cheras to Seremban, connecting Selangor Railway to Sungei Ujong Railway and providing direct connectivity from Prai to the north to Port Dickson to the south.

Swettenham's proposal was approved by the Colonial Office under the justification wide-ranging transport linkages would allow access to land for use in agriculture and diversify the region's sources of revenue, while improving administrative efficiency by linking the FMS with the Straits Settlements (widening the scope of the plan to include additional linkages to the Straits Settlements of Malacca and Singapore).

Construction of the connections began in 1897 and concluded in 1903 with the Prai-Port Dickson line completed. The FMSR was founded in 1901 in the process, combining assets of Perak Railway and Selangor Railway as the two railway networks were the first to be connected. Management of stations and railways within the two networks were turned over to the FMSR, while locomotives originally operated by the two companies were absorbed into the FMSR and renumbered in July 1901. The amalgamation of other railway companies into the FMSR would follow in the coming years.

While the Prai-Port Dickson line was completed in 1903, extensions were still required to connect the network with Malacca and Singapore. The extension southwards led to the formation of two short-lived railway companies largely intended to oversee the construction of lines within their state borders.

The Malacca Government Railway (MGR) was awarded a concession by the state government for the construction a railway line between Tampin and Malacca Town, as well as an extension of the main line between Malacca's state border with Negeri Sembilan that leads to Gemas. Upon completion of the lines, the MGR was absorbed into the FMSR in 1905.