Asymmetry of the neonatal brain is not yet understood at the level of structural connectivity. We utilized DTI deterministic tractography and structural network analysis based on graph theory to determine the pattern of structural connectivity asymmetry in 124 normal neonates. We tracted white matter axonal pathways characterizing interregional connections among brain regions and inferred asymmetry in left and right anatomical network properties. Our findings revealed that in neonates, small-world characteristics were exhibited, but did not differ between the two hemispheres, suggesting that neighboring brain regions connect tightly with each other, and that one region is only a few paths away from any other region within each hemisphere. Moreover, the neonatal brain showed greater structural efficiency in the left hemisphere than that in the right. In neonates, brain regions involved in motor, language, and memory functions play crucial roles in efficient communication in the left hemisphere, while brain regions involved in emotional processes play crucial roles in efficient communication in the right hemisphere. These findings suggest that even at birth, the topology of each cerebral hemisphere is organized in an efficient and compact manner that maps onto asymmetric functional specializations seen in adults, implying lateralized brain functions in infancy.