Different attempts have been made in the past two decades to develop radiolabeled peptide conjugates with enhanced pharmacokinetic properties in order to improve the application for tumor imaging and peptide receptor radionuclide therapy (PRRT), which targets the cholecystokinin-2 receptor (CCK2R). In this paper, the influence of different side chain and peptide bond modifications has been explored for the minigastrin analog DOTA-DGlu-Ala-Tyr-Gly-Trp-(N-Me)Nle-Asp-1Nal-NH2 (DOTA-MGS5). Based on this lead structure, five new derivatives were synthesized for radiolabeling with trivalent radiometals. Different chemical and biological properties of the new derivatives were analyzed. Receptor interaction of the peptide derivatives and cell internalization of the radiolabeled peptides were studied in A431-CCK2R cells. The stability of the radiolabeled peptides in vivo was investigated using BALB/c mice. Tumor targeting of all 111In-labeled peptide conjugates, and of a selected compound radiolabeled with gallium-68 and lutetium-177, was evaluated in BALB/c nude mice xenografted with A431-CCK2R and A431-mock cells. All 111In-labeled conjugates, except [111In]In-DOTA-[Phe8]MGS5, showed a high resistance against enzymatic degradation. A high receptor affinity with IC50 values in the low nanomolar range was confirmed for most of the peptide derivatives. The specific cell internalization over time was 35.3-47.3% for all radiopeptides 4 h after incubation. Only [111In]In-DOTA-MGS5[NHCH3] exhibited a lower cell internalization of 6.6 ± 2.8%. An overall improved resistance against enzymatic degradation was confirmed in vivo. Of the radiopeptides studied, [111In]In-DOTA-[(N-Me)1Nal8]MGS5 showed the most promising targeting properties, with significantly increased accumulation of radioactivity in A431-CCK2R xenografts (48.1 ± 9.2% IA/g) and reduced accumulation of radioactivity in stomach (4.2 ± 0.5% IA/g). However, in comparison with DOTA-MGS5, a higher influence on the targeting properties was observed for the change of radiometal, resulting in a tumor uptake of 15.67 ± 2.21% IA/g for [68Ga]Ga-DOTA-[(N-Me)1Nal8]MGS5 and 35.13 ± 6.32% IA/g for [177Lu]Lu-DOTA-[(N-Me)1Nal8]MGS5.