Burkholderia sp. strain WSM4176 is an aerobic, motile, Gram-negative, non-spore-forming rod that was isolated from an effective N2-fixing root nodule of Lebeckia ambigua collected in Nieuwoudtville, Western Cape of South Africa, in October 2007. This plant persists in infertile, acidic and deep sandy soils, and is therefore an ideal candidate for a perennial based agriculture system in Western Australia. Here we describe the features of Burkholderia sp. strain WSM4176, which represents a potential inoculant quality strain for L. ambigua, together with sequence and annotation. The 9,065,247 bp high-quality-draft genome is arranged in 13 scaffolds of 65 contigs, contains 8369 protein-coding genes and 128 RNA-only encoding genes, and is part of the GEBA-RNB project proposal (Project ID 882).