Membrane peptide folding studies require peptides that bind to lipid vesicles while remaining water-soluble. Currently available peptides are either artificial designs, or they have membrane-disrupting antimicrobial or venomous activity. As a first step to derive new soluble membrane-binding peptides from naturally occurring membrane proteins, we trained a learning algorithm on several water-soluble and insoluble helical peptides by comparing its predictions with experimental solubility and fluorescence vesicle binding assays. The algorithm yielded an easily computed score S to discover soluble peptides in databases of transmembrane helical proteins. To validate the algorithm, we selected four helices based on a good S score. Experiments showed that all four are soluble at >25 mu M, and that three bind to vesicles. We illustrate with an example that the vesicle binding of such peptides can be temperature-tuned. Finally, we predict four additional peptides that should be water-soluble and able to bind to lipid vesicles.