For a polycyclic-by-finite group Gamma, of Hirsch length h, an affine (resp. polynomial) structure is a representation of Gamma into Aff(R-h) (reap. P(R-h), the group of polynomial diffeomorphisms) letting Gamma act properly discontinuously on R-h Recently it was shown by counter-examples that there exist groups Gamma (even nilpotent ones) which do not admit an affine structure, thus giving a negative answer to a long-standing question of John Milnor. We prove that every polycyclic-by-finite group Gamma admits a polynomial structure, which moreover appears to be of a special (''simple'') type (called ''canonical'') and, as a consequence of this, consists entirely of polynomials of a bounded degree. The construction of this polynomial structure is a special case of an iterated Seifert Fiber Space construction, which can be achieved here because of a very strong and surprising cohomology vanishing theorem.