The oral administration of peptide drugs is hampered by their metabolic instability and limited intestinal uptake. Here, we describe a method for the generation of small target-specific peptides (less than 1,600 Da in size) that resist gastrointestinal proteases. By using phage display to screen large libraries of genetically encoded double-bridged peptides on protease-resistant fd bacteriophages, we generated a peptide inhibitor of the coagulation Factor XIa with nanomolar affinity that resisted gastrointestinal proteases in all regions of the gastrointestinal tract of mice after oral administration, enabling more than 30% of the peptide to remain intact, and small quantities of it to reach the blood circulation. We also developed a gastrointestinal-protease-resistant peptide antagonist for the interleukin-23 receptor, which has a role in the pathogenesis of Crohn's disease and ulcerative colitis. The de novo generation of targeted peptides that resist proteolytic degradation in the gastrointestinal tract should help the development of effective peptides for oral delivery.