Directionally solidified (DS) NiAl–Mo eutectic composites were strained to plastic strain values ranging from 0% to 12% to investigate the origin of the previously observed stochastic versus deterministic mechanical behaviors of Mo-alloy micropillars in terms of the development of dislocation structures at different pre-strain levels. The DS composites consist of long, [1 0 0] single-crystal Mo-alloy fibers with approximately square cross-sections embedded in a [1 0 0] single-crystal NiAl matrix. Scanning transmission electron microscopy (STEM) and computational stress state analysis were conducted for the current study. STEM of the as-grown samples (without pre-straining) reveal no dislocations in the investigated Mo-alloy fibers. In the NiAl matrix, on the other hand, a〈1 0 0〉-type dislocations exist in two orthogonal orientations: along the [1 0 0] Mo fiber axis, and wrapped around the fiber axis. They presumably form to accommodate the different thermal contractions of the two phases during cool down after eutectic solidification. At intermediate pre-strain levels (4–8%), a/2〈1 1 1〉-type dislocations are present in the Mo-alloy fibers and the pre-existing dislocations in the NiAl matrix seem to be swept toward the interphase boundary. Some of the dislocations in the Mo-alloy fibers appear to be transformed from a〈1 0 0〉-type dislocations present in the NiAl matrix. Subsequently, the transformed dislocations in the fibers propagate through the NiAl matrix as a〈1 1 1〉 dislocations and aid in initiating additional slip bands in adjacent fibers. Thereafter, co-deformation presumably occurs by 〈1 1 1〉 slip in both phases. With a further increase in the pre-strain level (>10%), multiple a/2〈1 1 1〉-type dislocations are observed in many locations in the Mo-alloy fibers. Interactions between these systems upon subsequent deformation could lead to stable junctions and persistent dislocation sources. The transition from stochastic to deterministic, bulk-like behavior in sub-micron Mo-alloy pillars may therefore be related to an increasing number of multiple a〈1 1 1〉 dislocation systems within the Mo fibers with increasing pre-strain, considering that the bulk-like behavior is governed by the forest hardening of these junctions.