Some demonstrative embodiments include devices, systems and/or methods of establishing a wireless beamformed link. For example, an apparatus may include a wireless communication controller to control a first wireless communication device to communicate millimeter-wave (mmWave) signals with a second wireless communication device over a mmWave frequency band, the mmWave signals including signals transmitted according to a plurality of different transmit (Tx) beamforming settings, the wireless communication controller is to control the first wireless communication device to communicate feedback information, which is based on the mmWave signals, over a non-mmWave frequency band, and to control the first wireless communication device to establish with the second wireless communication device a beamformed link over the mmWave frequency band, the beamformed link using a Tx beamforming setting, which is determined based on the feedback information.