This paper addresses the lack and need for specialized and visually effective interaction design guidance for sub-sea military operations. We identify gaps in the implementation of best practice visualization techniques, building upon our recently published survey on visual interfaces used in military decision support systems. Our analysis focuses on the current NATO symbology standard and several sub-sea military frontend systems to identify deficiencies and their underlying causes. Such origins of deficiencies include inadequate design consideration of environmental conditions, as well as incomplete hardware and software requirements for sub-sea conditions. While many such gaps exist, for the purposes of this paper, we narrow our focus to exploring the potential for a new sub-sea symbology for the maritime domain, drawing from insights gained and developed through our participation in the EDIDP (European Defence Industrial Development Programme) project CUIIS (Comprehensive Underwater Intervention Information System). We propose extending existing NATO military standards by creating a comprehensive framework for a new sub-sea symbology and visual interaction design. This framework includes a set of semiotic communication symbols for military divers, which can easily be combined based on the most common messages required for effective communication between command and military divers. This paper concludes by highlighting the opportunities for improvement in NATO Military Symbology for sub-sea military operations.