A distributor storage network with last-mile delivery can be used to achieve the supply chain management objective of high responsiveness. The fourth party logistics network design problem with last-mile delivery is an important research in the network design problem, which needs to be solved by simultaneously making decisions on issues of the distribution center location, the selection, allocation and routing programming of the third party logistics. A mix-integer programming model is established to minimize the total system cost with satisfying the constraints of vehicle routing programming and flow conservation and so on. Because the problem is NP-hard, this paper presents a two-phase heuristic algorithm for the fourth party logistics network design problem with last-mile delivery by dividing the problem into two subproblems. The algorithm solves the subproblems in an iterative manner. In the numerical tests, by comparing with the solutions calculated by the CPLEX and the particle swarm optimization algorithm, the heuristic algorithm outperforms the other two algorithms, which illustrates that the heuristic algorithm can provide an efficient solution to the fourth party logistics network design problem with last-mile delivery; meanwhile, the heuristic algorithm is successfully applied in the experiment of practical scale, which also shows that it can offer an effective tool in the field.