Methods and apparatus relating to fast deskew when exiting a low-power partial-width high speed link state are described. In one embodiment, an exit flit on active lanes and/or a wake signal/sequence on idle lanes may be transmitted at a first point in time to cause one or more idle lanes of a link to enter an active state. At a second point in time (following or otherwise subsequent to the first point in time), training sequences are transmitted over the one or more idle lanes of the link. And, the one or more idle lanes are deskewed in response to the training sequences and prior to a third point in time (following or otherwise subsequent to the second point in time). Other embodiments are also disclosed and claimed.