Superfruit guava (Psidium guajava L.) is one of the healthiest fruits due to its high antioxidant dietary fiber and vitamin content. However, the growth and development of this plant are severely affected by salinity stress, mostly at the seedling stage. MicroRNAs (miRNAs) are small, noncoding, endogenous, highly conserved RNA molecules that play key regulatory roles in plant development, organ morphogenesis, and stress response signaling. In this study, applying computational approaches and following high stringent filtering criteria, a total of 40 potential microRNAs belonging to 19 families were characterized from guava. The identified miRNA precursors formed stable stem-loop structures and exhibited high sequence conservation among diverse and evolutionarily distant plant species. Differential expression pattern of seven selected guava miRNAs (pgu-miR156f-5p, pgu-miR160c-5p, pgu-miR162-3p, pgu-miR164b-5p, pgu-miR166t, pgu-miR167a-5p, and pgu-miR390b-5p) were recorded under salinity stress and pgu-miR162-3p, pgu-miR164b-5p as well as pgu-miR166t were found to be the most affected ones. Using the psRNATarget tool, a total of 49 potential target transcripts of the characterized guava miRNAs were identified in this study which are mostly involved in metabolic pathways, cellular development, and stress response signaling. A biological network has also been constructed to understand the miRNA mediated gene regulation using the minimum free energy (MFE) values of the miRNA-target interaction. To the best of our knowledge, this is the first report of guava miRNAs and their targets.