With advance in manufacturing technology, 45ºand 135º diagonal segments can be permitted in an octilinear routing model. In this article, we present the first heuristic algorithm to solve obstacle-avoiding octilinear Steiner minimal tree (OAOSMT) construction problem. We first constructs an obstacle-free Euclidean minimal spanning tree (OFEMST). Then two lookup tables about OFEMST are generated, which can provide fast information inquire for subsequent steps. Next, an obstacle-avoiding strategy is proposed to convert OFEMST into an obstacle-avoiding octilinear Steiner tree (OAOST). Finally, we design an excellent refinement technique, which can further reduce the wirelengh. Multiple sets of standard test cases have been tested in C language. Experimental results show that the proposed algorithm achieves the best results in terms of both wirelengh and runtime. It is extremely practical and useful in the process of VLSI routing.