Neisseria gonorrhoeae (gonococcus) is the causative agent of gonorrhea and is the second most commonly notified sexually transmitted infection in Australia. One of the highest notification rates of gonorrhea is found in the remote and indigenous populations of Western Australia (WA). Unlike isolates from the Perth metropolitan areas, the remote indigenous isolates have low rates of antimicrobial resistance. Population structure and whole-genome comparison of 59 isolates from the Western Australian N. gonorrhoeae collection was used to investigate strain relatedness of isolates in the metropolitan and regional areas. Core genome phylogeny, MLST, Neisseria gonorrhoeae multi-antigen sequence typing (NG-MAST) and Neisseria gonorrhoeae sequence typing for antimicrobial resistance (NG-STAR) in addition to hierarchical clustering of sequences using hierBAPS tool were used to characterise the isolates. Population structure analysis of the 59 isolates with 72 isolates from an international collection, revealed six population groups suggesting N. gonorrhoeae is a weakly clonal species. AMR genotypes were variably associated with each of the six population groups. Two distinct population groups WAG1 and WAG2 represented 63% of WA isolates and were mostly composed of the remote indigenous isolates that carried no chromosomal AMR genotypes. In contrast, the metropolitan isolates belonged to population groups found in the international database and were frequently multi-drug resistant, suggesting international transmission of the isolates. Our study highlights the population structure of N. gonorrhoeae is distinct between the communities in remote WA and the men who have sex with men communities in urban WA. To our knowledge this is the first genomic epidemiological study of N. gonorrhoeae isolates from Australia. Given the high rate of antimicrobial resistance in metropolitan regions, ongoing surveillance is essential to ensure the enduring efficacy of the empiric treatment in the remote regions of WA.