The Māori Battalion's four rifle companies were organised along tribal lines, partly following the boundaries of the four Māori parliamentary electorates. Each company had its own nickname, reflecting the history and character of its main recruiting area:

• A Company, drawn from Ngāpuhi, Ngāti Whātua and other northern iwi, was known as the Gum Diggers (Ngā Kiri Kapia) due to the long history of kauri gum digging in the north.
• B Company, centred on Te Arawa and the Mataatua tribes, was the Penny Divers (Ngā Ruku Kapa) - a reference to the practice of diving for coins to entertain tourists in the Rotorua thermal region.
• C Company, drawn from the Tairāwhiti/East Coast region, was the Cowboys (Ngā Kaupoi), because of the common use of horses for transport in that area.
• D Company, which covered the whole of the South Island and the remainder of the North Island, including Waikato, Taranaki, Manawatū and Wairarapa, was known as the Foreign Legion or Ngāti Walkabout.
• Headquarters (HQ) Company drew its personnel from all over Māoridom. Its diverse origins and roles earned it the name Odds and Sods.