This research explores the development of flight connections multi-leg searching. It applies the concept of graph theory and Partial Constraint Satisfaction Problem (Partial CSP). Current practices of information retrieval for flight connections usually provide the users with only one-leg of network which restricts the scope of information that users could retrieve in planning their flight itinerary. This research is aimed at developing a flight connections searching system that is able to give suggestion to users of broader destination network for their itinerary. The suggested destinations are selected based on Partial CSP technique. Instead of using Constraint Satisfaction technique, Partial CSP has been proposed to be implemented in this research as its approach could solve over-constrained problem. A web-based prototype has been developed to explain the concept of multi-leg searching. The development will be continued by adopting Partial CSP in future works. © 2010 IEEE.