A technique dynamically assigns priorities to traffic engineering (TE) label switched paths (LSPs) from a head-end node of a computer network. The novel technique increases the ability to place TE-LSPs that would be otherwise blocked by bandwidth fragmentation. Specifically, a head-end node allocates a range of priority values for groups of possible TE-LSP configurations, such as, e.g., groups by type and/or size of the possible TE-LSPs. When requesting a TE-LSP, the head-end node attempts to establish the TE-LSP by dynamically increasing a priority value of the TE-LSP within the corresponding range of priority values until adequate resources are available, at which time the head-end node may establish the TE-LSP. Upon expiration of a configurable timer, the head-end node dynamically decreases the priority value of the established TE-LSP within the corresponding range of priority values and determines whether the established TE-LSP can lower its priority yet still obtain adequate resources along a path with an acceptable cost. If so, the head-end node may reestablish the TE-LSP at the lower priority value.