Some demonstrative embodiments include devices, systems and/or methods of establishing a connection between a cellular node and a core network. For example, a first Evolved Node B (eNB) may include a cellular transceiver to communicate with a User Equipment (UE); an X2 interface to communicate with at least one second eNB; and a controller to send to the second eNB a first message including a core network node discovery request, to receive from the second eNB a second message including a core network node identifier, and to establish an S1 connection between the first eNB and a core network using the core network node identifier.