A computational procedure, PEPFLEX-II, for calculating multiple peptide solution conformations from NMR data is reported. It combines restrained simulated annealing for structural calculations, an ensemble averaged full relaxation matrix approach for NOE back calculation, and an iterative NOE restraint modification procedure into a protocol whose goal is to calculate the maximum range of peptide conformations consistent with the experimental data. The distance restraint modification is achieved by systematically increasing the upper boundary of the distance restraints when NOE violations occur. By using looser distance restraints and using a relatively small NOE "force constant" in the simulated annealing, the procedure allows the molecule to search over a wider conformational space. The result is an improved fit of the calculated NOE’s for the ensemble to the original experimental NOE data. Two convergence criteria are used to test whether both the best fit of the experimental NOE data and the maximum coverage of conformational space are achieved. The PEPFLEX-II procedure has been applied to the nanopeptide desmopressin in aqueous solution, for which several well-defined structural families were generated. The structures satisfy all the criteria for "good NMR structures", and their ensemble average fits the experimental NOE data better than any one individual structure.