The molecular mechanisms by which vascular tissues acquire their identities are largely unknown. Here, we report on the identification and characterization of VASCULATURE COMPLEXITY AND CONNECTIVITY (VCC), a member of a 15-member, plant-specific gene family in Arabidopsis (Arabidopsis thaliana) that encodes proteins of unknown function with four predicted transmembrane domains. Homozygous vcc mutants displayed cotyledon vein networks of reduced complexity and disconnected veins. Similar disconnections or gaps were observed in the provasculature of vcc embryos, indicating that defects in vein connectivity appear early in mutant embryo development. Consistently, the overexpression of VCC leads to an unusually high proportion of cotyledons with high-complexity vein networks. Neither auxin distribution nor the polar localization of the auxin efflux carrier were affected in vcc mutant embryos. Expression of VCC was detected in developing embryos and procambial, cambial, and vascular cells of cotyledons, leaves, roots, hypocotyls, and anthers. To evaluate possible genetic interactions with other genes that control vasculature patterning in embryos, we generated a double mutant for VCC and OCTOPUS (OPS). The vcc ops double mutant embryos showed a complete loss of high-complexity vascular networks in cotyledons and a drastic increase in both provascular and vascular disconnections. In addition, VCC and OPS interact physically, suggesting that VCC and OPS are part of a complex that controls cotyledon vascular complexity.