Definite polychaetes appeared in the Cambrian. For example, this is Canadia, from the Middle Cambrian Burgess Shale of British Columbia.
Canadia and other Cambrian polychaetes had no jaws, but some later polychaetes developed hard jaws, which are sometimes mineralized with iron oxide. Such polychaete jaws are fairly common in the fossil record, and are known as scolecodonts. Numerous well-preserved scolecodonts have been found in Silurian strata of Gotland, Sweden; these have been assigned to five genera, and more than 20 species. Thus, there is good evidence that the polychaetes were already a diverse group over 400 million years ago.
Other polychaete fossils include tracks and burrows. Many sedentary polychaetes secrete a lining for their burrows, or at least around their body, and these tubes may be found as fossils. Whole body fossils of polychaetes are rarer, being generally restricted to Lagerstatten -- localities with unusually good preservation of fossils. Mazon Creek, near downtown Chicago, is one of these localities where polychaetes have been found.
Bergman, C. F. 1989. Silurian paulinitid polychaetes from Gotland. Fossils and Strata 25:1-128.