Some demonstrative embodiments include devices, systems and/or methods of communication over common control channels. For example, an apparatus may include logic and circuitry configured to cause a User Equipment (UE) to determine a selected Common Control Channel (CCCH) message configuration from a first predefined message configuration and a second predefined message configuration, the first predefined message configuration having a first predefined message bit-size, the second predefined message configuration having a second predefined message bit-size; to generate an Uplink (UL) CCCH message according to the selected CCCH message configuration, the UL CCCH message comprising a Medium Access Control (MAC) header comprising a Logical Channel Identify (ID) (LCID) field having a value corresponding to the selected CCCH message configuration; and to transmit the UL CCCH message to a Next Generation Node B (gNB) over a logical channel corresponding to the selected CCCH message configuration.