To measure the depth of fire-damaged concrete by ultrasonic method, it was traditionally assumed that the concrete of the fire-damaged structural member could be simply classified into damaged layer and undamaged layer. Based on it, the damage depth can be calculated with a series of single-sided ultrasonic measured data. This method is simple and convenient but less accurate in the practical application. To improve the algorithm, hyperbola curves are adopted to simulate the varying of damage with depth in this paper. And parabolic curves are adopted to simulate the traces of ultrasonic wave in different measured distances. Therefore, the minimum propagation time can be obtained under different damage conditions. Through comparing the calculating results and measured data in different measured distances, the most likely damaged trend can be determined with least square method. At the end of this paper, examples are demonstrated to prove this algorithm feasible and more accurate than the traditional one.