In this paper, we study an optimal execution problem in the case of uncertainty in market impact to derive a more realistic market model. Our model is a generalized version of that in Kato (2012), where a model of optimal execution with deterministic market impact was formulated. First, we construct a discrete-time model as a value function of an optimal execution problem. We express the market impact function as a product of a deterministic part (an increasing function with respect to the trader's execution volume) and a noise part (a positive random variable). Then, we derive a continuous-time model as a limit of a discrete-time value function. We find that the continuous-time value function is characterized by an optimal control problem with a L?vy process and investigate some of its properties, which are mathematical generalizations of the results in Kato (2012). We also consider a typical example of the execution problem for a risk-neutral trader under log-linear/quadratic market impact with Gamma-distributed noise.