This paper describes development of a fully implicit compositional simulator for modeling of asphaltene deposition during natural depletion. In this paper, a new approach for multiphase flash calculation has been developed. This approach provides a more detailed description of the kinetic part of asphaltene deposition which needs to be explained more clearly. Due to a large number of unknowns, there are many ways to solve such a system by choosing different sets of independent variables. A new set of independent variables in a fully implicit model is considered for asphaltene deposition modeling. By incorporating an asphaltene precipitation model into a compositional simulator where the phase equilibrium equations, the volumetric constraint equation, the component transport equations, the multiphase flash equations and the deposition equation are solved simultaneously; a simulator for asphaltene deposition was developed with respect to natural depletion. The pure solid model is used to model asphaltene precipitation. The solid particles are considered to be separated into three parts: precipitated, flocculated and deposited solid. A first-order chemical reaction is used which models forward and reverse rates for the conversion of precipitated asphaltene to flocculated asphaltene. Also, a deposition model including adsorption, pore throat plugging, and re-entrainment was used. The simulator can also predict formation damage including porosity and permeability reduction in each block.