Molecular mechanisms controlling arterial–venous specification have not been fully elucidated. Previously, we established an embryonic stem cell differentiation system and demonstrated that activation of cAMP signaling together with VEGF induces arterial endothelial cells (ECs) from Flk1+ vascular progenitor cells. Here, we show novel arterial specification machinery regulated by Notch and β-catenin signaling. Notch and GSK3β-mediated β-catenin signaling were activated downstream of cAMP through phosphatidylinositol-3 kinase. Forced activation of Notch and β-catenin with VEGF completely reconstituted cAMP-elicited arterial EC induction, and synergistically enhanced target gene promoter activity in vitro and arterial gene expression during in vivo angiogenesis. A protein complex with RBP-J, the intracellular domain of Notch, and β-catenin was formed on RBP-J binding sites of arterial genes in arterial, but not venous ECs. This molecular machinery for arterial specification leads to an integrated and more comprehensive understanding of vascular signaling.