Stingless bees accumulate deposits of plant resins that are mixed with beeswax to produce propolis. Previous studies have reported anti-microbial constituents of stingless bee (Tetragonula carbonaria) propolis from East Australia, but several components remained to be characterized. In the search of natural products yet unreported for Australian propolis, four bee deposit-resins of T. carbonaria bees were analysed by gas and liquid chromatography mass spectrometry with accurate mass measurements. Ethanolic extracts of the deposit-resins were tested in vitro against Staphylococcus aureus ATCC 25983 and Pseudomonas aeruginosa ATCC 27853 by the agar diffusion method. Phloroglucinols, flavonoids and isoprenoids were identified in samples. The crude extracts showed strong anti-staphylococcal effects but were less active against the Gram-negative bacterium. The diagnostic data enabled the identification of markers that can be used for profiling other Australian propolis sources and to target the isolation of bioactive phloroglucinols in future studies against antibiotic resistant S. aureus strains.