The clinical need for improved blood vessel substitutes, especially in small-diameter applications, drives the field of vascular tissue engineering. The blood vessel has a well-characterized structure and function, but it is a complex tissue, and it has proven difficult to create engineered tissues that are suitable for widespread clinical use. This review is focused on approaches to vascular tissue engineering that use proteins as the primary matrix or "scaffold" material for creating fully biological blood vessel replacements. In particular, this review covers four main approaches to vascular tissue engineering: 1) cell-populated protein hydrogels, 2) cross-linked protein scaffolds, 3) decellularized native tissues, and 4) self-assembled scaffolds. Recent advances in each of these areas are discussed, along with advantages of and drawbacks to these approaches. The first fully biological engineered blood vessels have entered clinical trials, but important challenges remain before engineered vascular tissues will have a wide clinical effect. Cell sourcing and recapitulating the biological and mechanical function of the native blood vessel continue to be important outstanding hurdles. In addition, the path to commercialization for such tissues must be better defined. Continued progress in several complementary approaches to vascular tissue engineering is necessary before blood vessel substitutes can achieve their full potential in improving patient care.