The Escherichia coli neutral M1-aminopeptidase (ePepN) is a novel target identified for the development of antimicrobials. Here we describe a solid-phase multicomponent approach which enabled the discovery of potent ePepN inhibitors. The on-resin protocol, developed in the frame of the Distributed Drug Discovery (D3) program, comprises the implementation of parallel Ugi-azide four-component reactions with resin-bound amino acids, thus leading to the rapid preparation of a focused library of tetrazole-peptidomimetics (TPMs) suitable for biological screening. By dose-response studies, three compounds were identified as potent and selective ePepN inhibitors, as little inhibitory effect was exhibited for the porcine ortholog aminopeptidase. The study allowed for the identification of the key structural features required for a high ePepN inhibitory activity. The most potent and selective inhibitor (TPM 11) showed a non-competitive inhibition profile of ePepN. We predicted that both diastereomers of compound TPM 11 bind to a site distinct from that occupied by the substrate. Theoretical models suggested that TPM 11 has an alternative inhibition mechanism that doesn't involve Zn coordination. On the other hand, the activity landscape analysis provided a rationale for our findings. Of note, compound TMP 2 showed in vitro antibacterial activity against Escherichia coli. Furthermore, none of the three identified inhibitors is a potent haemolytic agent, and only two compounds showed moderate cytotoxic activity toward the murine myeloma P3X63Ag cells. These results point to promising compounds for the future development of rationally designed TPMs as antibacterial agents.