Spatial genetic patterns are influenced by numerous factors, and they can vary even among coexisting, closely related species due to differences in dispersal and selection. Eucalyptus (L'Héritier 1789; the "eucalypts") are foundation tree species that provide essential habitat and modulate ecosystem services throughout Australia. Here we present a study of landscape genomic variation in two woodland eucalypt species, using whole-genome sequencing of 388 individuals of Eucalyptus albens and Eucalyptus sideroxylon. We found exceptionally high genetic diversity (π ≈ 0.05) and low genome-wide, interspecific differentiation (FST = 0.15) and intraspecific differentiation between localities (FST ≈ 0.01-0.02). We found no support for strong, discrete population structure, but found substantial support for isolation by geographic distance (IBD) in both species. Using generalized dissimilarity modelling, we identified additional isolation by environment (IBE). Eucalyptus albens showed moderate IBD, and environmental variables have a small but significant amount of additional predictive power (i.e. IBE). Eucalyptus sideroxylon showed much stronger IBD and moderate IBE. These results highlight the vast adaptive potential of these species and set the stage for testing evolutionary hypotheses of interspecific adaptive differentiation across environments.