The early promise of ferromagnet-semiconductor heterostructures (FMSH) and dilute magnetic semiconductors (DMS) as a basis for spintronics has led to serious challenges for both theorists and experimentalists. This talk will focus on three fundamental issues: basic physics of spin injection, multi-scale methodology for spin-dependent transport calculations and band engineering of highly efficient FMSH-based spin injectors and spin detectors. These issues are addressed using a combination of first-principles theory, analytical modeling of the underlying physics, and design and numerical simulation of spintronic devices. We will start from basic definitions of non-equilibrium spin polarizations of the current and electron density and derive some useful relations between these quantities. We will further consider a theory of spin injection within the linear-response approximation and its generalization to a non-linear case. We will formulate a self-consistent multi-scale scheme for spin-dependent transport calculations of FMSH. The scheme combines the large scale drift-diffusion equation approach and the small scale first-principles calculations of the spin-dependent transmission matrix to provide proper microscopic boundary conditions at both sides of the junction. We will demonstrate that spin polarization of electrons in nonmagnetic semiconductors near specially tailored FMSH junctions can achieve 100%. We propose several new devices based on DMS heterostructures that lead to potentially useful effects, including extremely large and tunable tunneling magnetoresistance and high-efficiency spin filtering. These prototype devices include GaMnAs/AlAs/GaMnAs tunnel junctions; double-barrier quantum well heterostructures; and spin-selective resonant interband tunneling devices in the InAs/AlSb/GaMnSb system, using ferromagnetic DMS quantum wells. This work is supported by ONR.