Cachexia is a devastating fat tissue and muscle wasting syndrome associated with every major chronic illness, including cancer, chronic obstructive pulmonary disease, kidney disease, AIDS, and heart failure. Despite two decades of intense research, cachexia remains under-recognized by oncologists. While numerous drug candidates have been proposed for cachexia treatment, none have achieved clinical success. Only a few drugs are approved by the FDA for cachexia therapy, but a very low success rate is observed among patients. Currently, the identification of drugs from herbal medicines is a frontier research area for many diseases. In this milieu, network pharmacology, transcriptomics, cheminformatics, and molecular docking approaches were used to identify potential bioactive compounds from herbal medicines for the treatment of cancer-related cachexia. The network pharmacology approach is used to select the 32 unique genes from 238 genes involved in cachexia-related pathways, which are targeted by 34 phytocompounds identified from 12 different herbal medicines used for the treatment of muscle wasting in many countries. Gene expression profiling and functional enrichment analysis are applied to decipher the role of unique genes in cancer-associated cachexia pathways. In addition, the pharmacological properties and molecular interactions of the phytocompounds were analyzed to find the target compounds for cachexia therapy. Altogether, combined omics and network pharmacology approaches were used in the current study to untangle the complex prognostic genes involved in cachexia and phytocompounds with anti-cachectic efficacy. However, further functional and experimental validations are required to confirm the efficacy of these phytocompounds as commercial drug candidates for cancer-associated cachexia.