Construction of the Johore Wooden Railway began in 1869, some 16 years before completion of the Taiping to Port Weld line in Perak which is often described as the first railway in Malaya.
The wooden railway was the brainchild of the ruler of Johor, Maharaja Abu Bakar (he did not assume the title of Sultan until 1885). Abu Bakar had toured Europe in 1866 where he would have seen how the rapid spread of railways was transforming the continent.
His idea was to build a short line (30 km) from Johor Bahru to Gunung Pulai, a 650 metre high hill covered in lush jungle with waterfalls which he envisioned would be a good location for a hill resort or sanatorium.
Work progressed slowly probably due to the technical challenges of building a railway with wooden rails and wooden sleepers held in place by wooden wedges. In 1875 Sir Andrew Clarke, who was Governor of the Straits Settlements, was invited over from nearby Singapore with his wife Lady Clarke to officiate at the naming ceremony of the railway's first and only locomotive which was named after her. They rode on the train for a mile or so which was as far as the track extended.
According to the Malayan Railways website, the locomotive was a second-hand Indian State Railways B class 0-404T.
The station is thought to have been located near where Johor Zoo now stands facing the elegant mosque bearing Abu Bakar's name.
By 1875 some 10 miles of track was reported as complete but thereafter the project appears to have been abandoned perhaps as the Maharaja realised that the mounting costs of building a railway to nowhere were never going to be worthwhile. The locomotive was sold off to the Selangor State Railway and within a few years the wooden rails were overgrown and eaten by termites.
It has been argued that the Maharaja never intended to build a viable railway and that his real objective was to promote his image as a modern ruler with vision and ambition in the eyes of the British so that they would leave Johor free of political interference.
You can read more about this story on Projek Keretapi Kita, an excellent and well-researched blog by Mahen Bala.