Most of the protein folding methods use information from known proteins to predict protein structure. For homology and fold recognition methods this information is used directly and good results can be obtained if a sufficient similar protein with known structure is found. However, if no such protein is available or for large unmatched regions, ab initio methods can be of great help (specially for small proteins). Our method uses a fragment library and a search technique to create possible structures from which a high scoring set can then be analysed. The search alternates between testing for possible fragments, and choosing stochastically one of the fragments using a score based on current and previous search information. Backtrack is performed if no fragments are available. When a structure is completed, a score is calculated using frequencies of contacts and buried state derived from known proteins. The score information is saved for use in the next structure searches and a new point in the search tree is stochastically chosen for constructing a new structure. The algorithm chooses points in previous constructed structures that had lower scores, trying to improve that structure.