Porphyromonas gingivalis has been extensively associated with both the onset and progression of periodontitis. We previously isolated and characterized two P. gingivalis strains, one from a patient exhibiting severe chronic periodontitis (CP3) and another from a periodontally healthy individual (H3). We previously showed that CP3 and H3 exhibit differences in virulence since H3 showed a lower resistance to cationic peptides compared with CP3, and a lower ability to induce proliferation in gingival epithelial cells. Here, we aimed to determine whether differences in virulence between these two strains are associated with the presence or absence of specific genes encoding virulence factors. We sequenced the whole genomes of both P. gingivalis CP3 and H3 and conducted a comparative analysis regarding P. gingivalis virulence genetic determinants. To do so, we performed a homology search of predicted protein sequences in CP3 and H3 genomes against the most characterized virulence genes for P. gingivalis available in the literature. In addition, we performed a genomic comparison of CP3 and H3 with all the 62 genomes of P. gingivalis found in NCBI’s RefSeq database. This approach allowed us to determine the evolutionary relationships of CP3 and H3 with other virulent and avirulent strains; and additionally, to detect variability in presence/absence of virulence genes among P. gingivalis genomes. Our results show genetic variability in the hemagglutinin genes. While CP3 possesses one copy of hagA and two of hagC, H3 has no hagA and only one copy of hagC. Experimentally, this finding is related to lower in vitro hemmaglutination ability of H3 compared to CP3. Moreover, while CP3 encodes a gene for a major fimbrium subunit FimA type 4 (CP3_00160), H3 possess a FimA type 1 (H3_01400). Such genetic differences are in agreement with both lower biofilm formation ability and less intracellular invasion to oral epithelial cells exhibited by H3, compared with the virulent strain CP3. Therefore, here we provide new results on the genome sequences, comparative genomics analyses, and phenotypic analyses of two P. gingivalis strains. The genomics comparison of these two strains with the other 62 genomes included in the analysis provided relevant results regarding genetic determinants and their association with P. gingivalis virulence.