Bacterial contamination of the membranes used during guided bone regeneration directly influences the outcome of this procedure. In this study, we analyzed the early stages of bacterial adhesion on two commercial dense polytetrafluoroethylene (d-PTFE) membranes in order to identify microstructural features that led to different adhesion strengths. The microstructure was investigated by X-ray diffraction (XRD), differential scanning calorimetry (DSC), and Fourier transform infrared (FTIR). The surface properties were analyzed by atomic force microscopy (AFM), scanning electron microscopy (SEM), and surface free energy (SFE) measurements. Bacterial properties were determined using the microbial adhesion to solvents (MATS) assay, and bacterial surface free energy (SFE) was measured spectrophotometrically. The adhesion of four species of oral bacteria (Streptococcus mutans, Streptococcus oralis, Aggregatibacter actinomycetemcomitas, and Veilonella parvula) was studied on surfaces with or without the artificial saliva coating. The results indicated that the degree of crystallinity (78.6% vs. 34.2%, with average crystallite size 50.54 nm vs. 32.86 nm) is the principal feature promoting the adhesion strength, through lower nanoscale roughness and possibly higher surface stiffness. The spherical crystallites (“warts”), observed on the surface of the highly crystalline sample, were also identified as a contributor. All bacterial species adhered better to a highly crystalline membrane (around 1 log10CFU/mL difference), both with and without artificial saliva coating. Our results show that the changes in polymer microstructure result in different antimicrobial properties even for chemically identical PTFE membranes.