Pooled fecal samples can be a cost-effective and specific way to test a herd for Mycobacterium avium subsp. paratuberculosis (MAP). The Animal Health Diagnostic Laboratory at Cornell University currently uses a liquid-culture method for rapid detection of MAP in bovine fecal samples. The objective of the study was to obtain the pool-size with the lowest cost given the herd size, expected prevalence in the herd, and the goal of the farmer. A stochastic spreadsheet model was developed to obtain estimates for the costs of pooled fecal sampling for pool-sizes between 1 and 30 cows. It was assumed that the whole herd is tested and that all animals in the herd are divided into equal sized pools. Moreover, the sensitivity (Se) of the test for pooled samples was supposed identical for heavy shedders when pool-size increased but the pool Se decreased for low and moderate shedders with a Log-formula per extra animal in a pool. The specificity (Sp) is set at 0.999. The number of positive pools in a herd was randomly determined based on the expected MAP prevalence. A pool was considered "high positive" when it contained at least one heavy shedder, "moderate positive" when it contains at least one moderate shedder but no high shedders and "low positive" when it only contains one or more low shedders. The individual samples of a positive pool were retested to identify the shedder in the pool and the total number of tests determined the total costs. The model showed that the optimal pool-size differed depending on the objective of the farm, the herd size, and the prevalence. An increased pool-size decreased the costs, increased the variation around the costs, and decreased the probability to detect the shedders. Pooling is not useful in smaller (<250 cows), low-prevalence (<5%) herds. In larger herds and herds with a higher prevalence, pooling is more cost-efficient than individual samples.