3D indoor navigation in multi-story buildings and under changing environments is still difficult to perform. 3D models of buildings are commonly not available or outdated. 3D point clouds turned out to be a very practical way to capture 3D interior spaces and provide a notion of an empty space. Therefore, pathfinding in point clouds is rapidly emerging. However, processing of raw point clouds can be very expensive, as these are semantically poor and unstructured data. In this article we present an innovative octree-based approach for processing of 3D indoor point clouds for the purpose of multi-story pathfinding. We semantically identify the construction elements, which are of importance for the indoor navigation of humans (i.e., floors, walls, stairs, and obstacles), and use these to delineate the available navigable space. To illustrate the usability of this approach, we applied it to real-world data sets and computed paths considering user constraints. The structuring of the point cloud into an octree approximation improves the point cloud processing and provides a structure for the empty space of the point cloud. It is also helpful to compute paths sufficiently accurate in their consideration of the spatial complexity. The entire process is automatic and able to deal with a large number of multi-story indoor environments.