Abstract: Addition chain for an integer corresponds to the number of multiplications in modular exponentiation using the integer as the exponent. Modular exponentiation is the basis of public key crypto systems. Finding an optimal addition chain is an NP-complete problem. Therefore, metaheuristic have been favored in searching for the near optimal solution. In this study we proposed probabilistic method for generating an initial solution to the problem, suitable for optimization using metaheuristic. It is aimed at providing foundation for an efficient constructive metaheuristic algorithm that can find high quality solution to the problem. To ensure diversity, the proposed method generates both star and non-star steps. It generates valid addition chain with diverse steps that is not far from optimal. Test on the generated chains also shows that a suitable metaheuristic can efficiently turn them to nearest optimal ones.