We investigate the performance of microwave-frequency phononic crystal resonators fabricated on thin-film lithium niobate for integration with superconducting quantum circuits. Fordifferent design geometries at millikelvin temperatures, we achieve mechanical internal quality factors Qi above 105−106 at high microwave drive power, corresponding to 5×106 phonons inside the resonator. By sweeping the defect size of resonators with identical mirror cell designs, we are able to indirectly observe signatures of the complete phononic bandgap via the resonators‘ internal quality factors. Examination of quality factors‘ temperature dependence shows how superconducting and two-level system (TLS) loss channels impact device performance. Finally, we observe an anomalous low-temperature frequency shift consistent with resonant TLS decay and find that material choice can help to mitigate these losses.