Recent advances in qubit fidelity and hardware availability have driven efforts to simulate molecular systems of increasing complexity in a quantum computer and motivated us to to design quantum algorithms for solving the electronic structure of periodic crystalline solids. To this effect, we present a hybrid quantum-classical algorithm based on Variational Quantum Deflation [Higgott et al., Quantum, 2019, 3, 156] and Quantum Phase Estimation [Dobv{s}iv{c}ek et al., Phys. Rev. A, 2007, 76, 030306(R)] to solve the band structure of any periodic system described by an adequate tight-binding model. We showcase our algorithm by computing the band structure of a simple-cubic crystal with one $s$ and three $p$ orbitals per site (a simple model for Polonium) using simulators with increasingly realistic levels of noise and culminating with calculations on IBM quantum computers. Our results show that the algorithm is reliable in a low-noise device, functional with low precision on present-day noisy quantum computers, and displays a complexity that scales as $Omega(M^3)$ with the number $M$ of tight-binding orbitals per unit-cell, similarly to its classical counterparts. Our simulations offer a new insight into the quantum mindset applied to solid state systems and suggest avenues to explore the potential of quantum computing in materials science.