A novel approach to robust optimization of coal blending operations is proposed. While many rigorous mathematical approaches have been developed for this problem in the past, most neglect the uncertainty associated with both the inherent coal quality attributes as well as the sampling and measurement protocols used to measure those attributes. This uncertainty may lead to the imprecise estimation of quality values and force operators to adopt a conservative blend strategy based on safety factors and simple heuristics. One promising approach to rigorously address this shortcoming is through robust optimization (RO), a unique approach to handle data with uncertain and unspecified statistical distributions. In the current work, we first derive a deterministic optimization problem using the premium/penalty structure in typical coal sales contracts. This formulation is then translated to a robust formulation and solved as a Mixed Integer Nonlinear Program (MINLP). A numerical example is presented to demonstrate the utility of the method and to compare the deterministic solution, as the most optimistic and risky blending plan, with the RO solution, as the more pessimistic, yet robust, plan. The proposed strategy can help decision-makers achieve the economic and strategic goals of the operation at acceptable risk levels.