Brucellosis is of great public health and economic importance worldwide. Detection of brucellosis currently relies on serologic testing of an antibody response to Brucella infection, which suffers from cross-sensitivities to other antibody responses. Here we present a new method for identifying Brucella exposure that is based on profiling volatile organic compounds (VOCs) in exhaled breath. Breath samples from Brucella-seropositive bison and controls were chemically analyzed and demonstrated statistically significant differences in the concentration profiles of five VOCs. A point-of-care device incorporating an array of nanomaterial-based sensors could identify VOC patterns indicative of Brucella exposure with excellent discriminative power, using a statistical algorithm. We show that the patterns were not affected by the animals' environment and that the discriminative power of the approach was stable over time. The Brucella-indicative VOCs and collective patterns that were identified in this pilot study could lead to the development of a novel diagnostic screening test for quickly detecting infected animals chute-side, pen-side, or even remotely in populations of free-ranging ungulates. The promising preliminary results presented encourage subsequent larger scale trials in order to further evaluate the proposed method.