Excessive instantaneous power consumption in VLSI circuits may reduce the reliability and performance of VLSI chips. Hence, to synthesize circuits with high reliability, it is essential to efficiently obtain a precise estimation of the maximum power dissipation. However, due to the inherent input-pattern dependence of the problem, it is intractable to conduct an exhaustive search for circuits with a large number of primary inputs. Hence, the practical approach is to generate a tight lower bound and an upper bound for maximum power dissipation within a reasonable amount of CPU time. In this paper, instead of using the traditional simulation-based techniques, we propose a novel approach to obtain a lower bound of the maximum power consumption using Automatic Test Generation (ATG) technique. Experiments with MCNC and ISCAS-85 benchmark circuits show that our approach generates the lower bound with the quality which cannot be achieved using simulation-based techniques. In addition, a Monte Carlo based technique to estimate maximum power dissipation is described. It not only serves as a comparison version for our ATG approach, but also generates a metric to measure the quality of a lower bound from a statistical point of view.