Seven samples of Brazilian red propolis were analyzed using palynological methodology. The samples originate from the Brazilian northeastern coastal region, three of which were from Alagoas, three from Bahia and one from the Paraíba state. Glandular trichomes were absent in the red propolis, as were sand, earth, quartz and stark grains that normally occur in geopropolis. The presence of pollen grains of Schinus ("aroeira") was considered characteristic in the red propolis sediments. The quantity of pollen grains of Protium (Burseraceae), another possible resinous plant taxon, was very small when compared with that of Schinus. This tree also occurs beyond the intertide mangrove vegetation. The three characteristic pollen types of mangrove vegetation, Rhizophora, Laguncularia and Avicennia, were recognized only in one sample from Bahia. Pollen grains of Dalbergia ecastophyllum, another red-resinous plant species occurring in the coastal areas of Alagoas, were never detected inside the sediment of the propolis samples. Cocos pollen grains are frequent. The palynological analysis was therefore confirmed by the multivariate analysis. The red propolis may be related mainly to resin of Schinus in the studied samples.