An attitude estimation algorithm, which combines Unscented Kalman Filter (UKF) and Fast Linear Attitude Estimator (FLAE), is proposed for integrated inertial/starlight attitude determination systems based on gyros and star trackers. The attitude quaternion is firstly determined by the FLAE algorithm which uses the measurement signal of star trackers, and then the determined attitude quaternion is served as the state variable for UKF. Furthermore, the gyros drift is estimated by UKF, and then the system errors are compensated. The attitude error of FLAE-UKF is approximately ± 1″, with no significant difference compared to the UKF. The gyro drift estimates of both the FLAE-UKF and the UKF reach 0.5°/h within 15–30 s. This indicates that the FLAE-UKF maintains the same accuracy as the UKF in both attitude angle estimation and gyro drift estimation. Under different sampling times, the computational cost of the FLAE-UKF is decreased by at least 1/20 compared to the UKF. This indicates that the FLAE-UKF achieves reduced computational cost while maintaining the same accuracy as the UKF.