This invention relates to phytases, polynucleotides encoding them, uses of the polynucleotides and polypeptides of the invention, as well as the production and isolation of such polynucleotides and polypeptides. In particular, the invention provides polypeptides having phytase activity under high temperature conditions, and phytases that retain activity after exposure to high temperatures. The phytases of the invention can be thermotolerant and/or thermostable at low temperatures, in addition to higher temperatures. The phytases of the invention can be used in foodstuffs to improve the feeding value of phytate rich ingredients. The phytases of the invention can be formulated as foods or feeds or supplements for either to, e.g., aid in the digestion of phytate. The foods or feeds of the invention can be in the form of pellets, liquids, powders and the like. In one aspect, phytases of the invention are stabile against thermal denaturation during pelleting; and this decreases the cost of the phytase product while maintaining in vivo efficacy and detection of activity in feed.