For public land management agency managers and staff, co-stewardship and co-management may just be another element of the job, but for Native peoples it’s their very life. This article details respectful Tribal consultation from Native California perspectives, the foundation upon which successful co-stewardship and co-management of public lands rests. For those managers and staff who are unfamiliar with the Tribes and Tribal communities in their area, we begin by providing a note about naming terminology and some sources for identifying Native groups who are/were historically located in a given area. From there, after introducing the concept of respectful Tribal consultation, we describe the relationship and trust-building process between Tribal governments and their designated representatives and public land management agency managers and other staff, relationships that must be proven and nurtured across time, rather than initiated as time- and process-challenged business arrangements. We also explicate “community protocol,” the etiquette, customs, and traditional ways of interacting that support, protect, and promote the community, so once you get to the “business” part of the relationship, there can be equality, honor, and respect within it. Next, we provide links to best-practice models, resources, and agreements for effective collaboration and consultation in the stewardship of public lands. We end by making a case for the integration of natural and cultural “resources” in the procedures and policies under which Tribal consultation and co-stewardship and co-management of public lands takes place. Many of these processes are time tested and active in current co-management projects.