In blockchains, transaction fees are fixed by the users. The probability for a transaction to be processed quickly increases with the fee level. In this paper, we study the transaction fee optimization problem in the Ethereum blockchain. This problem consists of determining the minimum price a user should pay so that its transaction is processed with a given probability in a given amount of time. To reach this goal, we define a new solution method based on a Monte Carlo approach to predict the probability that a transaction will be mined within a given time limit. Numerical results on real data highlight the quality of the results.