A number of fossils from the Cambrian have been described which look more or less like onychophorans. Some, such as the Middle Cambrian Burgess Shale form Aysheaia (shown at top above) are rather similar to living forms. Others, such as the infamous Hallucigenia, were armored with long spines; until very recently it was thought that Hallucigenia was not an onychophoran-like animal at all, but instead was a bizarre creature that stood and possibly "walked" on its spines (Ramskold, 1992). The picture on the bottom above shows a latex cast of a third such fossil, one of the earliest known: Xenusion, from early Cambrian sandstones of eastern Europe. This form was also armed with spines, although they were shorter that those of Hallucigenia. Only two specimens have been found so far. (The coin in the pictuere, added for scale, is a Russian ruble, roughly the size of an American nickel.)
All of these Cambrian forms differed from living onychophorans in being marine. They do not appear in the fossil record after the Cambrian (so far as we know). The earliest (and the only) fossil terrestrial onychophoran was found in the Pennsylvanian deposits of Mazon Creek, near Chicago, a locality that has yielded a great many fossils of soft-bodied organisms. The fossil is not very different from living onychophorans. (Thompson and Jones 1980)
Thompson, I. and Jones, D. 1980. A possible onychophoran from the middle Pennsylvanian Mazon Creek beds of northern Illinois. Journal of Paleontology 54: 588-596.