Systems and methods for air-ground message prioritization are provided. In one embodiment, an message communication system comprises: a first Class-of-Service and Priority Tagging Module configured to tag messages with a message tag, the message tag comprising a Class-of-Service tag and a Priority tag; a queue broker that includes a plurality of message queues, wherein each message queues is associated with a Class-of-Service defined by at least one datalink technology, wherein the queue broker assigns each of the messages to one of the plurality of message queues based on a Class-of-Service indicated by the Class-of-Service tag; and an on-board message broker that monitors datalink availability and current state indicators, wherein the on-board message broker communicates to the queue broker when to transition one or more of the message queues between a Prioritize-and-Store operating state and a Prioritize-and-Forward operating state based on the datalink availability and the current state indicators.