The antigen alpha4beta1 (very late antigen-4, VLA-4) plays an important role in the migration of white blood cells to sites of inflammation. It has been implicated in the pathology of a variety of diseases including asthma, multiple sclerosis, and rheumatoid arthritis. We describe a series of potent inhibitors of alpha4beta1 that were discovered using computational screening for replacements of the peptide region of an existing tetrapeptide-based alpha4beta1 inhibitor (1; 4-[N'-(2-methylphenyl)ureido]phenylacetyl-Leu-Asp-Val) derived from fibronectin. The search query was constructed using a model of 1 that was based upon the X-ray conformation of the related integrin-binding region of vascular cell adhesion molecule-1 (VCAM-1). The 3D search query consisted of the N-terminal cap and the carboxyl side chain of 1 because, upon the basis of existing structure-activity data on this series, these were known to be critical for high-affinity binding to alpha4beta1. The computational screen identified 12 reagents from a virtual library of 8624 molecules as satisfying the model and our synthetic filters. All of the synthesized compounds tested inhibit alpha4beta1 association with VCAM-1, with the most potent compound having an IC(50) of 1 nM, comparable to the starting compound. Using CATALYST, a 3D QSAR was generated that rationalizes the variation in activities of these alpha4beta1 antagonists. The most potent compound was evaluated in a sheep model of asthma, and a 30 mg nebulized dose was able to inhibit early and late airway responses in allergic sheep following antigen challenge and prevented the development of nonspecific airway hyperresponsiveness to carbachol. Our results demonstrate that it is possible to rapidly identify nonpeptidic replacements of integrin peptide antagonists. This approach should be useful in identification of nonpeptidic alpha4beta1 inhibitors with improved pharmacokinetic properties relative to their peptidic counterparts.