The gap between known protein sequences and structures is increasing rapidly and experimental methods alone will not be able to fill in this gap. Therefore it is necessary to use computational methods to predict protein structures. Template based modeling methods could be used for sequences, which have detectable relationship with sequences of one or more experimentally determined protein structures. For predicting the structure of proteins, which does not share a detectable sequence relationship with experimental structures, ab initio protein structure prediction techniques must be used. The methods under ab initio protein structure prediction category aim to predict the structure of a protein from the sequence information alone, without any explicit use of previously known structures. These methods use thermodynamic principles and try to identify the native structure of a protein as the global minimum of a potential energy landscape. However, such methods are computationally complex and are extraordinarily challenging. There has been significant progress in the development of ab inito protein structure prediction methods over the past few years. This review describes the basic principles, the complexity, challenges and recent progresses of ab initio protein structure prediction.