Според легендата, градът е основан от троянския принц Антенор през 1183 г.пр.н.е. Тази версия е спомената и в поемата "Енеид" на Вергилий. През 1274 бил екхумиран саркофаг, за който се твърдяло, че съхранявал останките на Антенор.
Римляните наричали града Патавиум. Съвременното Падуа е именен вариант на римското име Patavium след озвучаване на "т" от съседните гласни и синкопа на звука "и" в провизорния вариант Padaua.
Тук се изказва предположение, че римското име идва от израза "via patet" - удобнопроходим път (широк, открит път) от via - път и pateo, ui, - ere - открит съм.  Макар град Падуа да е разположен на река Бакилионе, той е бил разположен на пътя преминаващ през река Падус и оттук името да означава "път през река Падуа" - Patavium. Името Padan Etruria идва от келтското Po danu = Po river, от което идва и латинското име на реката Padus.