Since traceability of halal food is not talking any longer about one step backward and one step forward and only can be done in inbound logistic, therefore we have to do business process reengineering as a strategy and methodology to make it happens along logistic activities. As we know logistic activities consist of inbound and outbound logistic, where halal traceability in inbound logistic has been implemented quite well that is why we have to discuss it in outbound logistic as a scope in this research. One of the features of business process reengineering is to capture the existing process and represent new processes adequately. Business process modeling plays a crucial role in such efforts. This paper proposes a structure for modeling business process in order to capture essential concepts of tracing halal food in its distribution activities and represent them structurally. The structure possesses two main features suitable for business process modeling: one is that it can represent critical processes and the sequences in the distribution of halal food, and the other is that it shows how to trace during the distribution of halal food by the information provided. Since the problem of tracing halal food is a probability function, so we do formulation by stochastic dynamic programming to develop the computation model. The computation model is a mathematical model and then how it operates in the tracing processes should be figured out in its business process model. The objective function of this computation model is to minimize the cost of halal food traceability activities. The business process modeling method is illustrated by an order fulfillment tracing processes in the stages of distribution of halal food using BPMN. The use case of this business process model explains the role and the interaction of  the activities of the actors in doing transfer information of the halal food at their critical processes. The internal actors of the ecosystem are the distributor, retailer, transporter, and warehouse company while the external actors involve supplier of halal food and halal certification body and government as the parties that have responsibilities to assure the halalness of the food distributed in the market. When the business process model is valid, it will be simulated in halal food traceability system.