An execution time estimation device includes a program partitioning section that extracts partial programs partitioned by a conditional branch instruction or a function call instruction from a target program, a partial program execution time estimation calculating section that calculates the execution time of each of the partial programs to associate the leading instruction and the end instruction of each of the partial programs, and the calculated execution time with one another, a branch history information generating section that generates a branch history bit sequence which is a sequence of the true-false of the conditional branch instruction of when the target program is executed, an execution trace reproducing section that generates the execution sequences of the partial programs based on the branch history bit sequence, and an execution time estimation calculating section that adds the execution time of the partial programs based on the execution sequences of the partial programs.