Re-investigation of the culture broth of the marine bacterium Staphylococcus sp. (no. P-100826-4-6) afforded a new cyclic tetrapeptide namely staphylopeptide A (1), along with five known compounds, cyclo (L-prolyl-L-valine) (2), cyclo (L-prolyl-L-tyrosine), (3), cyclo (L-prolyl-L-alanine) (4), L-phenylalanine (5), and L-tryptophan (6). The structures of the isolated compounds were determined by extensive IR, 1D ( 1 H and 13C) and 2D ( 1 H-1 H COSY, HSQC, HMBC, and NOESY) NMR and HRFABMS spectral measurements. The antimicrobial activity of the isolated compounds (1–6) was evaluated.