The origin of Arulmigu Thendayuthapani Temple, Johor Bahru dates back to the year 1917 when one venerable man by the name of R.V. Perumal Naidu, sanctified the "Holy Vel" on a piece of land belonging to him in Jalan Kuel to erect a temple for Lord Muruga. As the saying goes that temple worship is the lifelong obligation of every Hindu, perhaps it was the will of God that he should start a temple not only for him to perform prayers but also for all Hindus to worship at the Temple.
For 22 long years the Temple was under his personal care and on 8.6.1939 Thiru R.V. Perumal Naidu moved to Malacca after handing over the administration of the Temple to a "Panchayat" of five people: Thiru V. Muthukrishnan Pillai, Thiru Kandiah Masonar, Thiru Muthiah of P.W.D, Thiru Thangavelu of the Government Printing Department and Thiru Munusamy of the P.W.D.
At the Annual General Meeting held on 29.4.1940, Thiru R.V. Perumal Naidu was unanimously elected as the Trustee, Thiru Venugopal Naidu as the Chairman and Thiru V. Muthukrishnan as the Honorary Secretary. Thiru R.V. Perumal Naidu agreed to donate the land permanently to the Hindu public, but before this could be completed, he passed away in April 1943.
Nevertheless, the Temple continued to be managed by a committee and what started off as a zinc shed slowly and gradually developed into a proper temple with the installation of a Moolasthanam and Parivara Theivangal. By late 1940's and the early 1950's the Temple had been somewhat established with proper Poojas and Ubayams.
In 1955, the late Thiru K.R. Nadeson Chettiar, a well-known businessman, became the President. He donated the statues of Vinayagar, Thendayuthapani, Idumbamoorthy and the Navagrahangal. The Consecration Ceremony "Kumbabishegam" was held on 2nd February, 1958.
By now, the Temple became a popular place of worship. The Moolamoorthy, Ayimpon Vinayagar and Lord Subramaniam, riding in procession with his Consorts, Valli and Theivaanai, were decorated with gold ornaments. K.R. Nadeson Chettiar served as President for 17 years, contributing immensely to the Temple's growth.
In the 1970's, following some administrative changes, the Official Assignee intervened and an interim committee managed the temple. After several transitions, on 6th December, 1977, a pro-tem management committee was elected. In 1980, an Ayimpon Statue of Devi Karumariamman was brought from Tamil Nadu and installed, with the Kumbabishegam conducted on 9.9.1980.
At the Annual General Meeting held on 3.11.1999, Dr. N.G. Baskaran was elected as President. His appointment was historic because for three generations his family had been at the helm of Arulmigu Thendayuthapani Temple — his grandfather Thiru Rengasamy Chettiar (1943–1944), his father Thiru K.R. Nadeson Chettiar (1955–1972), and Dr. N.G. Baskaran himself from 1979 onwards.
A Wedding Hall was constructed and declared open on 23.6.1984 by Y.B. Dato S. Subramaniam, Deputy Minister of Housing & Local Government. In 1991, the need for a new temple was recognised, and an ambitious reconstruction project was launched. On 15.3.1998, the ground-breaking ceremony was performed for the new temple.
The contract for temple sculpture works was awarded to S.T.M. Thaneermalayam Stapathy of Madurai, Tamil Nadu on 1.9.1998. With the successful completion of the new temple, the Consecration Ceremony of the Maha Kumbabishegam was held on 15th November, 1999 between 10:32 AM and 11:24 AM, performed by Dr. Pitchai Kurukal of Pillayar Patti and other Sivachariars.