Hematopoiesis is an essential process that evolved in multicellular animals. At the heart of this process are hematopoietic stem cells (HSCs), which are multipotent, self-renewing and generate the entire repertoire of blood and immune cells throughout life. Here we studied the hematopoietic system of Botryllus schlosseri, a colonial tunicate that has vasculature, circulating blood cells, and interesting characteristics of stem cell biology and immunity. Self-recognition between genetically compatible B. schlosseri colonies leads to the formation of natural parabionts with shared circulation, whereas incompatible colonies reject each other. Using flow-cytometry, whole-transcriptome sequencing of defined cell populations, and diverse functional assays, we identified HSCs, progenitors, immune-effector cells, the HSC niche, and demonstrated that self-recognition inhibits cytotoxic reaction. Our study implies that the HSC and myeloid lineages emerged in a common ancestor of tunicates and vertebrates and suggests that hematopoietic bone marrow and the B. schlosseri endostyle niche evolved from the same origin.