Nano-patterning has been shown to be a powerful tool for manipulating the vibrational modes of elastic structures, with applications such as optical-mechanical mode coupling. Inspired by these recent developments in phononic band engineering, we propose a nano-patterning scheme to enhance the superconducting transition temperature Tc in phonon-mediated nano-film superconductors, such as aluminum. Using the finite element method, we simulate the lattice vibrational modes of nano-patterned films within the Debye model. Our results show that periodic nano-patterning softens the lattice vibrational modes compared to bulk films. It also increases the density of states at high energies, resulting in a couple of percent enhancement in Tc. Moreover, we investigate connections to random matrix theory and provide an experimental design prescription to optimize nano-patterning for further enhancement of the superconducting transition temperature.