Marines in the field rely heavily on their ability to survey the human landscape for potential insurgents and other individuals of interest. To support this activity, the Marines Corps' Combat Hunter program trains a set of cognitive and perceptual skills that allow for rapid identification of critical anomalies (individuals or objects) in the environment by exploiting environmental, behavioral, and physiological cues. These cognitive and perceptual skills have potential applications for a variety of complex domains within the Marine Corps and other services. In the present study, we explored differences between experts and novices in this domain, which the Marines call combat profiling. We hypothesized that expertise in identifying anomalies is a function of several key factors that distinguish experts from novices in many domains. These factors are (1) the organization of knowledge and its representation, which constrains situation assessment and decision making from the top down; (2) perception, which triggers assessment from the bottom up; and (3) metacognition and reasoning. We found evidence of significant differences between experts and novices on all three factors. Based on our findings, we propose an instructional approach that encourages development of expert knowledge structures and perceptual behaviors through careful design and ordering of exploratory exercises, explicit instruction, and exercises that provide opportunity for deliberate practice. The instructional approach develops metacognitive and critical thinking skills by requiring the student to discover key concepts, to weave coherent stories from their observations, and to critically compare their solutions with those of experts. The instructional strategy is extensible to related domains such as social and cultural skills training.