The wave propagations of two dimensional phononic crystals composed of auxetic materials are studied. The periodic structures consist of square lattice air cylinders in a solid background made of auxetic material. The finite element method and plane wave expansion method are used to obtain the band structures of the phononic crystals. The effects of Poisson's ratio on the elastic wave propagation within the phononic crystal are investigated. The negative Poisson's ratio of the auxetic material is shown to have significant effect on the dispersion of the elastic wave within the periodic structures. The results reveal that the phononic crystals composed of auxetic materials can have a great potential for the design of novel acoustic devices.