Astaxanthin is a natural product of immense value. Its biosynthesis has been investigated extensively and typically requires the independent activity of two proteins, a β-carotene ketolase and β-carotene hydroxylase. Rational engineering of this pathway has produced limited success with respect to the biological production of astaxanthin. Random mutagenesis of the β-carotene ketolase has also been pursued. However, to date, no suitable method has been developed for the investigation of the β-carotene hydroxylase because β-carotene and zeaxanthin cannot be differentiated visually, unlike β-carotene and canthaxanthin. Thus, random mutagenesis and efficient selection of improved β-carotene hydroxylase clones is not feasible. Presented here are the steps required for the efficient generation of a β-carotene hydroxylase random mutagenesis library in Escherichia coli. Subsequently presented is a novel high-throughput screening method for the rapid identification of clones with enhanced β-carotene hydroxylase activity. The validity of the presented method is confirmed by functional expression of the mutated proteins, combined with accurate quantification of produced carotenoids. The developed method has potential applications in the development of biological systems for improved carotenoid biosynthesis, as well as robust astaxanthin production.