We have investigated the fabrication and computational modelling of threedimensional phononic crystals for the observation of full band gaps for thermal phonons at sub-kelvin temperatures. Self-assembled arrays of monodisperse polystyrene nanospheres have been fabricated using a vertical deposition technique. Optimal conditions for increasing crystal domain size and crystalline quality have been studied. In addition, the phononic band structure has been computed using the finite element method for the simple cubic lattice. The dependence of band structure on contact area between spheres has also been studied. For small enough contact area a large band gap is observed, predicting a strong influence on sub-Kelvin thermal transport.