We demonstrated a nanoscaled artificial phononic crystal composed of three-dimensionally ordered quantum dots (QDs) with functional acoustic properties. Femtosecond ultrasonic technique is used to investigate the lattice dynamics of this phononic nanocrystal. The measurement results indicate that three-dimensional ordering and uniformity of the QDs are important factors influencing the observed acoustic resonance at the forbidden bands. For well-arranged QDs, noticeable features of the phononic band gap and the associated phonon cavity mode can be found, while this nanocrystal also serves as an effective acoustic medium, or acoustic meta material, for low-frequency acoustic phonons.