This work presents a novel real-time algorithm for runway detection and tracking applied to unmanned aerial vehicles (UAVs). The algorithm relies on a combination of segmentation-based region competition and minimization of a particular energy function to detect and identify the runway edges from streaming video data. The resulting video-based runway position estimates can be updated using a Kalman filter (KF) that integrates additional kinematic estimates such as position and attitude angles, derived from video, inertial measurement unit data, or positioning data. This allows a more robust tracking of the runway under turbulence. The performance of the proposed lane detection and tracking scheme is illustrated on various experimental UAV flights conducted by the Saudi Aerospace Research Center (KACST), by the University of Texas, Austin, and on simulated landing videos obtained from a flight simulator. Results show an accurate tracking of the runway edges during the landing phase, under various lighting conditions, even in the presence of roads, taxiways, and other obstacles. This suggests that the positional estimates derived from the video data can significantly improve the guidance of the UAV during takeoff and landing phases.