Many of the efforts surrounding the development of the National Animal Identification System have encompassed the identification of livestock production and handling premises as well as individuals or herds of animals, whereas little effort has been directed toward the ultimate goal of animal traceback within 48 h. A mock data set representative of the Colorado cattle population was created for modeling of cattle traceability. Using this data set, algorithms were developed to complete rapid and accurate traceback and traceforward of animals or premises or both. On July 19, 2005, the Colorado Department of Public Health and Environment, in conjunction with the Colorado Department of Agriculture, conducted a test exercise pertaining to homeland security. The exercise team randomly identified animal number 926,583 (of the 2 million total animals) as a potentially infected animal of interest and requested a traceback of this animal. Traceback was accomplished in 215 s, and 540 primary coresident animals were identified. However, due to animal movements, the number of coresidents (animals exposed, directly or indirectly, to the animal of interest) expanded with coresidency level (level 1 = direct contact; level 2 = direct contact with an animal that had direct contact with the animal of interest; level 3 = direct contact with an animal that had contact with an animal that had direct contact with the animal of interest, etc.) to more than 1.2 million coresidents at level 4, and more than 90% of all animals identified as a coresident at some level. In addition to the coresidency results, the premises containing the coresidents were identified and sorted by the number of coresidents. Because of animal movement, all 19,391 premises included in the data set had coresidents at some level. This exercise demonstrated the capability of the developed algorithms to complete rapid traceback and the complexity of the resulting animal traceback output.