As the most Muslim populated country in the world, the availability of the Halal product in Indonesia become critical. In 2014 there are only 11.63% of marketed products in Indonesia are halal certified. The existence of a new system and software will be on-site and follow up audits stages that are essential to do. The purposes of this study are to develop the Halal Audit information system (HAIS) and evaluate the HAIS implementation based on the time-cost Trade-off approach using integer linear programming (ILP). In the development of HAIS, The HAIS architecture of a system was described using Unified Model Language (UML). A single case study in chicken slaughtering company was carried to apply the HAIS software and evaluate the HAIS implementation. The results indicate that Integer Linear Programming can be used to calculate the trade-off between time and cost of HAIS implementation activities, such as software programming activity and software testing activity.