Hanwoo is highly prized for its marbling ability and is the most important cattle breed in Korea. In order to maintain the integrity of the breed and for product certification purposes it is important to develop tools to confirm the origin of the products. Breed composition estimates based on a large number of molecular markers (e.g. HD SNP arrays) are highly accurate but expensive for routine usage. The identification of a reliable panel with a small number of markers will reduce costs and can enable broader adoption of the technology by industry. In this work a heuristic optimization method was used to find the most reliable subset of markers, from the Illumina BovineHD array, to estimate breed proportion in Hanwoo. Accuracies of breed proportion estimates above 90% can be achieved using as little as 200 markers. The best balance between accuracy and number of SNP was obtained with 500 markers achieving 94% accuracy. Rapid and cost effective breed composition prediction in Hanwoo cattle based on a SNP panel with at least 200 markers will help to certify the products with an acceptable accuracy and ensure breed purity within the breeding program. The method described herein is directly applicable to other breeds.