Due to the increasing use of generator-produced radiometal Gallium-68 (68Ga) in positron-emission tomography/computed tomography (PET/CT), reliable bifunctional chelators that can efficiently incorporate 68Ga3+ into biomolecules are highly desirable. In this study, we synthesized two new bifunctional chelators bearing one or two phosphonic acid functional groups, named p-SCN-PhPr-NE2A1P and p-SCN-PhPr-NE2P1A, with the aim of enabling facile production of 68Ga-based radiopharmaceuticals. Both chelators were successfully conjugated to LLP2A-PEG4, a very late antigen-4 (VLA-4) targeting peptidomimetic ligand, to evaluate their application in 68Ga-based PET imaging. NE2P1A-PEG4-LLP2A exhibited the highest 68Ga3+ binding ability with molar activity of 37 MBq/nmol under mild temperature and neutral pH. Excellent serum stability of 68Ga-NE2P1A-PEG4-LLP2A was observed, which was consistent with the result obtained from density functional theory calculation. The in vitro cell study showed that 68Ga-NE2P1A-PEG4-LLP2A had significantly longer retention in B16F10 cells comparing to the reported retention of 64Cu-NE3TA-PEG4-LLP2A, although the uptake was relatively lower. In the biodistribution and micro-PET/CT imaging studies, high tumor uptake and low background were observed after 68Ga-NE2P1A-PEG4-LLP2A was injected into mice bearing B16F10 tumor xenografts, making it a highly promising radiotracer for noninvasive imaging of VLA-4 receptors overexpressed in melanoma.