The modeling of blood flow through a compliant vessel requires solving a system of coupled nonlinear partial differential equations (PDEs). Traditional methods for solving the system of PDEs do not scale optimally, i.e., doubling the discrete problem size results in a computational time increase of more than a factor of 2. However, the development of multigrid algorithms and, more recently, the first-order system least-squares (FOSLS) finite-element formulation has enabled optimal computational scalability for an ever increasing set of problems. Previous work has demonstrated, and in some cases proved, optimal computational scalability in solving Stokes, Navier-Stokes, elasticity, and elliptic grid generation problems separately. Additionally, coupled fluid-elastic systems have been solved in an optimal manner in 2D for some geometries. This paper presents a FOSLS approach for solving a 3D model of blood flow in a compliant vessel. Blood is modeled as a Newtonian fluid, and the vessel wall is modeled as a linear elastic material of finite thickness. The approach is demonstrated on three different geometries, and optimal scalability is shown to occur over a range of problem sizes. The FOSLS formulation has other benefits, including that the functional is a sharp, a posteriori error measure.