Some demonstrative embodiments include devices, systems and methods of relay backhauling with millimeter wave carrier aggregation. For example, a first Relay Node (RN) may include a cellular transceiver configured to communicate with a Donor evolved Node B (DeNB) over a cellular frequency band of a Primary cell (PCell); a millimeter-wave (mmWave) transceiver to communicate with a second RN via a backhaul link over a mmWave frequency band of a Secondary cell (SCell) within the PCell; and a controller to process a Relay-Physical-Downlink-Control-Channel (R-PDCCH) message received by the cellular transceiver over the cellular frequency band of the PCell, the R-PD-CCH message including cross-carrier scheduling information to schedule a downlink allocation over the backhaul link, the controller to trigger the mmWave transceiver to receive a downlink data packet from the second RN during the downlink allocation.