A link startup method of a storage device connected to a host through a plurality of lanes includes performing an initialization operation in the storage device; establishing data communication through a connected transmission lane and a connected reception lane among the plurality of lanes; transmitting a high speed link up message to the host through the connected transmission lane of the storage device; and performing a link startup operation in a high speed mode through the connected transmission lane of the storage device and the connected reception lane of the host, based on the high speed link up message transmitted by the storage device.