Lacunae and canaliculi spaces of osteocytes are remarkably well preserved in fossilized bone and serve as an established proxy for bone cells. The earliest bone in the fossil record is acellular (anosteocytic), followed by cellular (osteocytic) bone in the jawless relatives of jawed vertebrates, the osteostracans, about 400 million years ago. Virtually nothing is known about the physiological pressures that would have initially favored osteocytic over anosteocytic bone. We apply focused ion beam-scanning electron microscopy tomography combined with machine learning for cell detection and segmentation to image fossil cell spaces. Novel three-dimensional high-resolution images reveal areas of low density around osteocyte lacunae and their canaliculi in osteostracan bone. This provides evidence for demineralization that would have occurred in vivo as part of osteocytic osteolysis, a mechanism of mineral homeostasis, supporting the hypothesis that a physiological demand for phosphorus was the principal driver in the initial evolution of osteocytic bone.