Potassium (K) in plants participates in a variety of physiological processes and is kept at a higher concentration than its soluble form in soil. Potassium solubilizing bacteria (KSB) release K from minerals. Arbuscular mycorrhizal (AM) fungi facilitate bacterial movement along their extraradical hyphae and improve plant K status. However, the interaction of KSB and AM fungi is rarely reported. This study aimed to isolate KSB and evaluate their interaction with AM fungi in promoting plant K uptake and growth. Soil was sampled from the rhizosphere of Robinia pseudoacacia in the southern area of the Loess Plateau, where soil available K is lower than plant demand. KSB from soil was isolated using a select medium in which K-feldspar is the only K source. KSB that showed an obvious dissolving circle and relatively high K solubilizing efficiency (over 20%) were isolated and identified. A pot experiment was conducted in a randomized design to evaluate the effect of KSB and AM fungi and their interaction. Four out of 12 isolated strains that showed high potassium solubilizing efficiency were from the genus Pseudomonas. Inoculation of KSB promoted the growth and K content of R. pseudoacacia. KSB showed a variety of (increase, decrease, and not-obvious) influences on the colonization status of R. irregularis. Co-inoculation of R. irregularis and KSB promoted plant growth, K content of the plant, and the available K in the growth substrate. This study provided a basis for the utilization of KSB and AM fungi as biofertilizers in the Loess Plateau.