Gastric cancer is the fifth most frequent cancer and the third major cause of mortality worldwide. Helicobacter pylori, a bacterial infection linked with GC, injects the cytotoxin-associated antigen A (CagA; an oncoprotein) into host cells. When the phosphorylated CagA protein enters the cell, it attaches to other cellular components, interfering with normal cellular signaling pathways. CagA plays an important role in the progression of GC by interacting with phosphatidylserine of the host cell membrane. Therefore, disrupting the CagA–phosphatidylserine connection using small molecules appears to be a promising therapeutic approach. In this report, we screened the natural compounds from ZINC database against the CagA protein using the bioinformatics tools. Hits were initially chosen based on their physicochemical, absorption, distribution, metabolism, excretion, and toxicity (ADMET) characteristics, as well as other drug-like characteristics. To locate safe and effective hits, the PAINS filter, binding affinities estimation, and interaction analysis were used. Three compounds with high binding affinity and specificity for the CagA binding pocket were discovered. The final hits, ZINC153731, ZINC69482055, and ZINC164387, were found to bind strongly with CagA protein, with binding energies of −11.53, −10.67, and −9.21 kcal/mol, respectively, which were higher than that of the control compound (−7.25 kcal/mol). Further, based on binding affinity and interaction pattern, two leads (ZINC153731, ZINC69482055) were chosen for molecular dynamics (MD) simulation analysis. MD results showed that they displayed stability in their vicinity at 100 ns. This study suggested that these compounds could be used as possible inhibitors of CagA protein in the fight against GC. However, additional benchwork tests are required to validate them as CagA protein inhibitors.