Bacterial endophytes are crucial for the survival of many terrestrial plants, but little is known about the presence and importance of bacterial endophytes of marine plants. We conducted a survey of the endophytic bacterial community of the long-living Mediterranean marine angiosperm Posidonia oceanica in surface-sterilized tissues (roots, rhizomes, and leaves) by Denaturing Gradient Gel Electrophoresis (DGGE). A total of 26 Posidonia oceanica meadows around the Balearic Islands were sampled, and the band patterns obtained for each meadow were compared for the three sampled tissues. Endophytic bacterial sequences were detected in most of the samples analyzed. A total of 34 OTUs (Operational Taxonomic Units) were detected. The main OTUs of endophytic bacteria present in P. oceanica tissues belonged primarily to Proteobacteria (α, γ, and δ subclasses) and Bacteroidetes. The OTUs found in roots significantly differed from those of rhizomes and leaves. Moreover, some OTUs were found to be associated to each type of tissue. Bipartite network analysis revealed differences in the bacterial endophyte communities present on different islands. The results of this study provide a pioneering step toward the characterization of the endophytic bacterial community associated with tissues of a marine angiosperm and reveal the presence of bacterial endophytes that differed among locations and tissue types.