We will propose a branch and bound algorithm for solving a portfolio optimization model under nonconvex transaction costs. It is well known that the unit transaction cost is larger when the amount of transaction is small while it remains stable up to a certain point and then increases due to illiquidity effects. Therefore, the transaction cost function is typically nonconvex. The existence of nonconvex transaction costs very much affects the optimal portfolio particularly when the amount of fund is small. However, the portfolio optimization problem under nonconvex transaction cost are largely set aside due to its computational difficulty. In fact, there are only a few studies which treated nonconvex costs in a rigorous manner. In this paper, we will propose a branch and bound algorithm for solving a mean-absolute deviation portfolio optimization model assuming that the cost function is concave. We will use a linear underestimating function for a concave cost function to calculate a good bound, and demonstrate that a fairly large scale problem can be solved in an efficient manner using the real stock data and transaction cost table in the Tokyo Stock Exchange. Finally, extension of our algorithm to rebalancing will be briefly touched upon.