The town of Padukka is thought to have been founded as a camp site by the forces of the Seethawaka Kingdom in the 16th century CE, on the banks of the Pusweli Oya (a major tributary of Kelani Ganga river), at a location where the Arukwathu Oya (stream) joins the Pusweli Oya. It was a well-protected site with marshland and hills surrounding the site. Legend says that the town got its name as it was under the "Naa" (Iron Wood) Trees in the town that the Portuguese Army rested after being defeated by the Army of King Seethawa Rajasinghe in the battle at the adjoining Hanwella Fort. It was said that the defeated Portuguese army rested there until they settled their minds. Thus in the Sinhala Language it was called "Paha Dukka" ("paha"= vanish; "dukka"= sadness), which became "Padukka" (පාදුක්ක) later. The famous "Naa" (Iron Wood) Trees are still present at the town's rest house premises.