Methods and apparatus to select composite link cost-out thresholds are disclosed. A disclosed example method comprises collecting traffic statistics for a communication network, computing, based on the collected traffic statistics, a plurality of flow rates for a composite link of the communication network for respective ones of a plurality of potential fault conditions for the composite link, computing a plurality of remaining capacities of the composite link for respective ones of the plurality of fault conditions, computing a plurality of differences between respective ones of the plurality of flow rates and the plurality of remaining capacities, and selecting a cost-out threshold for the composite link based on the plurality of computed differences.