A method of communication link accessibility aware navigation is provided that includes querying a communication link accessibility map based on a location of interest provided by a path planner for a communication node. A communication link accessibility indicator is received representing a communication link characteristic associated with the location of interest in response to querying the communication link accessibility map. A communication link accessibility weight is determined based on a mission priority of maintaining a communication link of the communication node. The communication link accessibility weight is applied to the communication link accessibility indicator.