Airline and travel Web sites have demonstrated usability problems with the flight and fare search mechanisms. These problems appear in the query formulation, result display and locating optimal fares with fewest queries. This paper describes an approach to improve the usability of these airline reservation Web sites by employing proposed design guidelines and advanced search algorithm that exploits the user's scheduling and budget constraints to determine the optimal search space. The design guidelines and search process were tested with a prototype against two production Web sites. Results show that the design guidelines and search algorithm increase user ability to successfully complete a search and cover the search space to find the optimal fare. Users demonstrated better comprehension of the search results and reduced number of queries when searching for a low fare.